Quicksort: Partition Around a Pivot, Then Sort Each Side

Quicksort is a sorting algorithm that picks one item, the pivot, moves every smaller item to its left and every other item to its right, and then sorts the two sides by calling itself on each. This card covers that rearranging step, called a partition, the order the calls run in on seven numbers, and the signs that quicksort is the sort to reach for.

After a partition the pivot is in its final place. Every item to its left is smaller and every item to its right is at least as large, so no later step will move it. The two sides are still unsorted inside, but no item ever has to cross from one side to the other, so each side can be sorted on its own, and once both are sorted the whole array is. There is no merge step: merge sort does its work combining the halves, and quicksort does all of its work in the partition.

Sorting 7 2 8 1 5 3 6 shows the order of the calls. This version always takes the last item of the range as its pivot. The trace has one frame per partition: low and high mark the range being partitioned, and pivot marks the index where the pivot landed.

Four partitions sorted seven items. A range of one item, or of none, is never partitioned: it is the base case, already sorted. The pivots in this run split their ranges reasonably well, 6 landing at index 4 of 0 to 6. Had every pivot been the largest or smallest item of its range, each partition would have set aside a single item, and the calls would have gone n − 1 deep instead of about log₂ n.

Lining a class up by height works the same way. Pick Sam, send everyone shorter than Sam to the left and everyone else to the right, and Sam is standing exactly where Sam belongs; then do the same inside each group. The analogy breaks on the choice. A teacher picks someone of middling height by eye, while quicksort picks its pivot without looking at the others, and an unlucky pick leaves one group empty and the other holding everyone.

Cutting 7 2 8 1 5 3 6 at its middle position, into 7 2 8 and 1 5 3 6, and sorting each part is not quicksort. The parts overlap in value, so sorting them gives 2 7 8 and 1 3 5 6, which still have to be merged: that is merge sort. A partition divides by value, and that is what lets quicksort skip the merge.

Three signs point to quicksort. The items are numbers or other keys where equal items cannot be told apart, so stability does not matter. Memory is tight, and merge sort's O(n) buffer is more than you can spare. And speed on typical inputs matters more than a guarantee on every input: each partition compares every item with one fixed value and walks the array in order, which modern hardware does quickly, and a random pivot makes the slow case a matter of extraordinary bad luck rather than of any particular input. Where the worst case has to be ruled out entirely, the libraries that use quicksort guard it, as Java's Arrays.sort on primitive arrays does by switching to heapsort when the recursion runs too deep.