Quick sort: place the pivot, then sort each side

Merge sort sorts a million values in at most about 20 million comparisons, whatever their order, but it needs a buffer as long as the array. The sorts in sorting in code need no buffer, but make up to about n²/2 comparisons: 500 billion for a million values.

Quick sort usually gets the best of both. Pick one value, the pivot, and move every smaller value to its left and every other value to its right. The pivot is now exactly where it belongs, and no value will ever cross it again. Sort each side the same way and the array is sorted, with nothing to merge and no buffer.

"Usually" is the catch: the speed depends on how evenly the pivots split the values, and the simplest rule, taking the last value, is at its worst on an already sorted list.

pivot

The value a partition compares every other value with. This version takes the last value of the part.

partition

One pass over a part that moves the values smaller than the pivot before it and the rest after it. The pivot ends in its final place.

boundary i

During a partition, the position where the next smaller value goes. Everything before i is smaller than the pivot.

in place

Sorting inside the array itself, with a few variables and the call stack as the only extra memory.

average and worst case

The average is the mean cost over every order of the input; the worst case is the most any input can cost.

Here are 8 values. Play the run and watch the boundary i and the two sides grow.

A partition walks j along the part once and keeps one boundary, i: values before i are smaller than the pivot, values from i to j − 1 are at least the pivot, and the rest are unseen. A smaller A[j] swaps into position i and the boundary moves up one; otherwise j just moves on. Finally the pivot swaps into position i, between the two sides. This is Lomuto's partition; Tony Hoare's original walks two indices in from both ends and swaps less often.

Merge sort splits by position for free and compares afterwards, in the merges. Quick sort does all its comparing before its recursive calls, and afterwards there is nothing left to do: two sorted sides around a pivot already in place make a sorted part.

A partition of m values compares the other m − 1 with the pivot, once each. If pivots split parts roughly in half, as 45 split 8 values into 4 and 3, each level costs fewer than n comparisons, and there are about log₂ n levels.

Pivots don't need to be perfect. A random order mixes good and bad ones, and they average out to O(n log n): about 25 million comparisons for a million values, a third more than merge sort makes. Quick sort usually runs faster anyway: its inner loop is tiny, and it works within one array, which suits a computer's cache.

At n = 64 quick sort makes about 360 comparisons and merge sort about 310, far below n²/2. Doubling n from 32 multiplies their counts by about 2.4 and 2.5, the mark of n log n.

Before each comparison, predict which side of the pivot the value goes to. Smaller values go left. A value equal to the pivot goes right, because the test in the code panel is A[j] < pivot. This list holds two 45s, and one of them is the first pivot.

Here is one partition on its own, as the visualiser runs it, on [7, 2, 9, 4, 1, 6] with 6 as the pivot. It returns the pivot's final index.

def partition(a, lo, hi):
    pivot = a[hi]
    i = lo
    for j in range(lo, hi):
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[hi] = a[hi], a[i]
    return i

nums = [7, 2, 9, 4, 1, 6]
p = partition(nums, 0, len(nums) - 1)
print('pivot at ' + str(p))
print(*nums)

The rest of quick sort is a few lines: if the part holds two or more values, partition it, then sort lo to p − 1 and p + 1 to hi. But look at the second line printed: 2 4 1 6 9 7.

Those swaps have another side effect: quick sort is not stable, since a long swap can carry a value past others equal to it. In the Predict run, the 45 that started last was the first pivot and landed in position 3, ahead of the 45 that started in position 5. Equal plain numbers can't be told apart, so for them that's harmless: Java sorts arrays of numbers with a dual-pivot quick sort, but objects with a stable merge sort.

The cost rides on where the pivots land. Here is this version's worst input.

Reversed input is as bad, with the pivots alternating between the smallest and largest value left, and so is one value repeated, since values equal to the pivot all go right. A million sorted values would take about 500 billion comparisons. The first challenge in Break it runs this quick sort on 10 values you choose: make it reach its worst, 45 comparisons, where a random order takes about 24.

Every move is a swap inside the array, so there is no buffer. But watch depth among the variables: it reaches 11 on the sorted run and 5 on the Random one.

• A partition puts smaller values left of the pivot and the rest right, so the pivot lands in its final place; then each side is sorted the same way, with all the comparing before the recursive calls.
• A partition of m values costs m − 1 comparisons. Even splits give about log₂ n levels: O(n log n) on average.
• If every pivot is the smallest or largest value left, as with the last value of a sorted list, the cost is n(n − 1)/2 comparisons. Random pivots and median-of-three make that rare; introsort rules it out.
• It sorts in place, but its call stack is O(log n) deep on average and up to n deep at worst; recursing into the smaller side caps it at O(log n). It is not stable.
• Next: heap sort, which uses a heap to sort in place in O(n log n) even at worst (its visualiser), and quickselect, which partitions and goes into only the side holding the k-th position: O(n) on average. Practise with Kth Largest Number in a List and Closest Points to the Origin, or make the swaps yourself in Be the algorithm.