quicksort.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N;
    static int[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(bf.readLine());
        arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(bf.readLine());
        }
        int left = 0;
        int right = N - 1;
        quick(arr,left,right);


        for (int i = 0; i < N; i++) {
            System.out.print(arr[i] + " ");
        }
    }
    static void quick(int[] arr, int left, int right){
        int pl = left;
        int pr = right;
        int mid = arr[(right+left) / 2];

        do {
            while (arr[pl] < mid) pl++;
            while (arr[pr] > mid) pr--;
            if (pl <= pr) {
                int temp = arr[pr];
                arr[pr] = arr[pl];
                arr[pl] = temp;
                pr--;
                pl++;
            }
        }while (pl <= pr);

        if(left < pr) quick(arr,left,pr);
        if(pl< right) quick(arr,pl,right);
    }
}