fun quickSort(array: IntArray, left: Int, right: Int) {
    if (left >= right) {
        return;
    }
    val x = array[(left + right+1) shr 1]
    var i = left - 1;
    var j = right + 1;
    while (i < j) {
        do {
            i++
        } while (array[i] < x)
        //此时 arrar[i] >=x
        do {
            j--
        } while (array[j] > x)
        //此时 array[j] <=x
        if (i < j) {
            array[i] = array[j].also { array[j] = array[i] }
        }
    }


    quickSort(array, left, i-1)
    quickSort(array, i, right)
}

fun main() {
    val array = intArrayOf(1, 3, 2, 4, 5, 6, 7, 8, 9, 10)
    quickSort(array, 0, array.size - 1)
    array.forEach {
        print("%d\t".format(it))
    }
}

public class Main {
    public static void main(String[] args) {
        var scanner = new Scanner(System.in);
        var s = scanner.nextLine();
        var s1 = scanner.nextLine();
        var size = Integer.parseInt(s);
        var s2 = s1.split(" ");
        var ints = new int[size];
        for (int i = 0; i < size; i++) {
            ints[i] = Integer.parseInt(s2[i]);
        }
        quickSort(ints, 0, size - 1);
        for (int i = 0; i < size; i++) {
            System.out.print(ints[i] + " ");
        }
    }

    public static void quickSort(int[] array, int left, int right) {
        if (left >= right) {
            return;
        }
        int x = array[(left + right + 1) >> 1];
        int i = left - 1;
        int j = right + 1;
        while (i < j) {
            do {
                i++;
            } while (array[i] < x);
            do {
                j--;
            } while (array[j] > x);
            if (i < j) {
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        quickSort(array, left, i - 1);
        quickSort(array, i, right);
    }
}

Q.E.D.