Quick sort

Lomuto keeps one boundary i: everything left of i is smaller than the pivot. A scan pointer j moves right, and each smaller value is swapped into position i. At the end the pivot is swapped into index i, its final position. It is short and easy to get right.

Hoare uses two pointers that start at the ends and move toward each other. i stops at a value that belongs on the right, j stops at a value that belongs on the left, and they swap. It does about three times fewer swaps than Lomuto on average, but the pivot does not finish at a known index, so the recursion is on [lo..p] and [p+1..hi].

1public static void quickSort(int[] arr, int lo, int hi) {
2    if (lo >= hi) return;
3    int p = partition(arr, lo, hi);
4    quickSort(arr, lo, p - 1);
5    quickSort(arr, p + 1, hi);
6}
7
8static int partition(int[] arr, int lo, int hi) {
9    movePivotToEnd(arr, lo, hi);          // strategy: last, first, middle, median of 3
10    int pivot = arr[hi];
11    int i = lo;                            // arr[lo..i-1] < pivot
12    for (int j = lo; j < hi; j++) {
13        if (arr[j] < pivot) {
14            swap(arr, i, j);
15            i++;
16        }
17    }
18    swap(arr, i, hi);                      // pivot to its final place
19    return i;
20}

1public static void quickSort(int[] arr, int lo, int hi) {
2    if (lo >= hi) return;
3    int p = partition(arr, lo, hi);
4    quickSort(arr, lo, p);
5    quickSort(arr, p + 1, hi);
6}
7
8static int partition(int[] arr, int lo, int hi) {
9    int pivot = arr[lo + (hi - lo) / 2];
10    int i = lo - 1, j = hi + 1;
11    while (true) {
12        do { i++; } while (arr[i] < pivot);
13        do { j--; } while (arr[j] > pivot);
14        if (i >= j) return j;
15        swap(arr, i, j);
16    }
17}

The pivot decides how balanced the split is. A good pivot is near the median, so each side is about half the array and the recursion has log₂ n levels. A pivot that is the minimum or maximum leaves one side empty and the other with n - 1 elements.

Common strategies are the last or first element (simple, but terrible on sorted input), the middle element (fine for sorted input, but an adversary can still build a bad input), median of three (take the median of first, middle and last), and a random element. In the animation, change the Pivot option and run “Sorted, last pivot (worst)” and then “Sorted, middle pivot”: 28 comparisons versus 13 for 8 values.

Choose the pivot uniformly at random from arr[lo..hi]. No particular input can be consistently bad, because the running time depends on the random choices and not on the data. The expected number of comparisons is about 1.39 · n · log₂ n.

Swap the chosen element to the end, then use Lomuto as usual. Use ThreadLocalRandom in Java, since Math.random() is shared across threads and slower.

1private static int randomizedPartition(int[] arr, int lo, int hi) {
2    int r = lo + ThreadLocalRandom.current().nextInt(hi - lo + 1);
3    swap(arr, r, hi);                 // move the random pivot to the end
4    return partition(arr, lo, hi);    // Lomuto, pivot = arr[hi]
5}

With many equal keys, two-way partitioning keeps recursing on elements that are already equal to the pivot. Three-way (Dutch national flag) partitioning splits into < pivot, = pivot and > pivot. The equal band is finished immediately and is never sorted again.

Maintain four regions with three indices: [lo..lt-1] < pivot, [lt..i-1] = pivot, [i..gt] unexamined and [gt+1..hi] > pivot. When arr[i] > pivot swap it with arr[gt] and decrement gt, but do not advance i, because the value swapped in has not been examined yet. An array of all equal keys is sorted in one pass: run “All equal”.

1public static void quickSort3(int[] arr, int lo, int hi) {
2    if (lo >= hi) return;
3    int pivot = arr[lo + (hi - lo) / 2];
4    int lt = lo, i = lo, gt = hi;
5    while (i <= gt) {
6        if (arr[i] < pivot) swap(arr, lt++, i++);
7        else if (arr[i] > pivot) swap(arr, i, gt--);
8        else i++;
9    }
10    quickSort3(arr, lo, lt - 1);
11    quickSort3(arr, gt + 1, hi);
12}

The worst case happens when every partition is as lopsided as possible: sizes 0 and n - 1. The work is (n - 1) + (n - 2) + … + 1 = n(n - 1)/2 comparisons, and the recursion depth reaches n, which can overflow the stack on large arrays.

Typical triggers are sorted or reverse sorted input with a first or last pivot, and all-equal input with two-way partitioning. Production sorts defend against it with median-of-three or random pivots, three-way partitioning, and a fallback to heap sort once recursion gets too deep (introsort, see lesson 18.07).

Quick sort makes two recursive calls, and the second is a tail call. Java does not eliminate tail calls, so instead recurse into the smaller side and loop on the larger side. The smaller side is at most half the size, so the stack depth is at most log₂ n even when the partitions are badly unbalanced.

This bounds stack space to O(log n) in the worst case, although time may still be O(n²).

1static void quickSort(int[] arr, int lo, int hi) {
2    while (lo < hi) {
3        int p = partition(arr, lo, hi);
4        if (p - lo < hi - p) {        // left side is smaller: recurse into it
5            quickSort(arr, lo, p - 1);
6            lo = p + 1;               // then loop on the larger right side
7        } else {
8            quickSort(arr, p + 1, hi);
9            hi = p - 1;
10        }
11    }
12}