Quick Sort

Task: Sort this array in ascending order

void quickSort(int[] a, int lo, int hi) {    if (lo >= hi) return;    int p = partition(a, lo, hi);    quickSort(a, lo, p - 1);    quickSort(a, p + 1, hi);} int partition(int[] a, int lo, int hi) {    int pivot = a[hi];    int i = lo;    for (int j = lo; j < hi; j++) {        if (a[j] <= pivot) {            swap(a, i++, j);        }    }    swap(a, i, hi);    return i;}

What you are watching

Quick sort picks one value as a pivot and rearranges the array so that everything smaller sits to its left and everything larger to its right. That single pass puts the pivot in its final position for good, and leaves two smaller problems of the same shape to solve the same way. Partitioning 6, 2, 8, 3, 9, 4 around 4 splits it into a side of two and a side of three, and each side is then partitioned in turn. No merging step is needed, and no second array - the work happens in the row itself.