Sorting is the problem that most other structures in this course quietly depend on: binary search needs sorted data, and heaps and balanced trees are partly ways of avoiding repeated sorting. The earlier unit on merge sort for linked lists showed how to merge and split by relinking nodes. Here we treat arrays and answer three questions: why do merge sort and quicksort work, what do they cost, and can any algorithm that only compares keys do asymptotically better than ?
Definitions
Definition 18.2.1
(Comparison sort, stable sort and in-place sort)
A comparison sort receives a sequence and may learn about the keys only by asking whether for chosen positions. It outputs a permutation of the input in nondecreasing key order. A sort is stable if records with equal keys keep their input order, and in place if it uses only extra cells beyond the array (we shall relax this to for the recursion stack of quicksort). The cost counted below is the number of key comparisons in the worst case over all inputs of length , unless a different case is named.
Merge sort on arrays
Merge sort sorts by sorting the two halves recursively and merging them through a temporary array.
def merge_sort(a, lo, hi):
if hi - lo <= 1:
return
mid = (lo + hi) // 2
merge_sort(a, lo, mid)
merge_sort(a, mid, hi)
left, right = a[lo:mid], a[mid:hi]
i = j = 0
for k in range(lo, hi):
if j == len(right) or (i < len(left) and left[i] <= right[j]):
a[k] = left[i]; i += 1
else:
a[k] = right[j]; j += 1
Theorem 18.2.2
(Correctness and cost of array merge sort)
For a segment of length , merge_sort(a, lo, hi) leaves the segment sorted in nondecreasing order, with the same elements as before and with records of equal keys in their input order. For the worst-case number of comparisons satisfies and , and hence .
Proof
(Induction on the length, and the merge invariant)
Correctness. Induct on the length . A segment of length at most one is sorted. For longer segments both halves are strictly shorter, so by hypothesis they are sorted after the two recursive calls. In the merge loop, the invariant is: before writing position , the positions hold the smallest elements of the two halves in sorted order, and every remaining element of left[i:] and right[j:] is at least as large as each of them. Taking the smaller of the two heads preserves this because each remaining suffix is sorted. Taking the left head on ties makes the sort stable, since left records precede right records in the input. Every element is written exactly once, so the segment keeps the same elements.
Cost. Merging elements makes at most comparisons, because each comparison writes one element and the last element is written without a comparison. Hence for the worst case satisfies
Unrolling, level of the recursion consists of merges of size , costing less than comparisons per level, and there are levels. So , and for general the same bound holds up to a constant because the halves have sizes and . The temporary arrays need extra cells.
Proof X-ray
Where the merge invariant uses sortedness and the tie rule
The induction hypothesis enters the merge exactly once: it says that left and right are each sorted, so the first remaining element of each is the smallest remaining element of its half. The smaller of the two heads is then the smallest of all remaining elements, which is why writing it preserves the claim that every remaining element is at least as large as each written one. The written prefix stays sorted because each element written is no larger than everything still remaining, in particular the next one written.
The tie rule does not affect sortedness. It matters only for stability: when left[i] == right[j], taking the left head keeps the left record, which came earlier in the input, ahead of the right one. The loop closes when : every element has been written, no suffix remains, and the invariant says that the whole segment is the sorted sequence of all its elements.
Quicksort
Quicksort chooses a pivot, rearranges the segment so that smaller keys lie before the pivot and larger keys after it, and recurses on the two sides.
Definition 18.2.3
(Lomuto partition of a[lo..hi])
Take the pivot and keep an index , initially . For : if , increase by one and swap with . Finally swap with and return .
The loop invariant, before each value of , is that contains only keys at most , contains only keys greater than , and . At the end the pivot sits at position with every key to its left at most and every key to its right greater than , so it is in its final place.
quicksort(a, lo, hi) partitions, then calls itself on and where is the returned index. Termination: both calls are on segments strictly shorter than the original, since the pivot is excluded. Correctness follows by induction: after partitioning the pivot is final, and each side is sorted by hypothesis and contains exactly the keys that belong there. A partition of elements makes exactly comparisons.
Theorem 18.2.4
(Quicksort cost)
(a) If the pivot is always the smallest or largest key of its segment, quicksort makes comparisons. (b) If the pivot is chosen uniformly at random from each segment and the keys are distinct, the expected number of comparisons is at most .
Proof
(Recurrence for the worst case, indicator probabilities for the average)
For (a), the recurrence is , which sums to . With the last element as pivot, an already sorted array triggers exactly this behavior.
For (b), name the keys in sorted order. Two keys are compared at most once, because a comparison always involves the current pivot, and a pivot is then placed in its final position and never takes part again. Keys and with are compared exactly when the first pivot chosen among is or : if some with is chosen first, it separates them into different sides forever. By symmetry each of the keys is equally likely to be chosen first, so the probability is . By linearity of expectation,
using .
Concept lensStructural
Quicksort's pivots form a search tree
Make each chosen pivot a node whose left and right children are the pivots of the two recursive calls. Smaller keys go left and larger keys right, so this is a binary search tree on the keys. A comparison always pairs a pivot with a key of its segment, that is, with a descendant, and each such pair is compared exactly once. Hence the number of comparisons equals the sum of the node depths, with the root at depth . For sorted input with the last key as pivot the tree is a chain of four nodes, with depths , matching the example below.
Quicksort is in place apart from its recursion stack, which is if we always recurse on the smaller side first and loop on the larger. It is not stable.
The lower bound
Theorem 18.2.5
(Comparison-sorting lower bound)
Every comparison sort that correctly sorts all inputs of distinct keys makes at least comparisons on some input. Moreover , so the worst-case number of comparisons is .
Proof
(Counting the leaves of a decision tree)
Fix a deterministic algorithm and a length . Each execution is a sequence of comparisons, and the next comparison depends only on earlier answers. This gives a binary tree: internal nodes are comparisons, edges are the two answers, and each leaf is a final output permutation. Different input orderings of distinct keys must reach different leaves, since a leaf prescribes one fixed rearrangement and two different orderings need different rearrangements to become sorted. There are orderings, so there are at least leaves. A binary tree of height has at most leaves, hence and . The height is the worst-case number of comparisons.
For the asymptotic form, . This product has factors, each at least , so for .
Proof X-ray
What the leaf count assumes
The argument has one move: instead of analyzing how a particular algorithm behaves, it counts how many different outcomes any correct algorithm must be able to produce. Three hypotheses are each used in one place. Determinism makes the next comparison a function of the earlier answers, which turns an execution into a path in a binary tree. Correctness on every input forces each leaf to name one fixed rearrangement, so two different orderings cannot share a leaf. Distinct keys are what make the orderings need different rearrangements: if all keys are equal, every rearrangement already gives a sorted sequence, so the count says nothing about such inputs.
The proof closes by squeezing the number of leaves between two bounds, . The halving of the product afterwards only converts into the explicit form .
Consequently merge sort is asymptotically optimal among comparison sorts, and quicksort matches it in expectation. The bound says nothing about algorithms that inspect keys in other ways, such as counting by digits.
Worked examples
Worked example 18.2.6
(Merge sort on eight keys)
Sort . The halves and are sorted recursively. In the first half, becomes with 1 comparison and stays with 1 comparison; merging with compares , , and gives (3 comparisons). In the second half, and cost 1 each; merging compares , , and gives (3 comparisons).
The final merge of and compares (take 1), (tie, take the left 2), (take the right 2), (take 3), (take 4), (take 5), (take 6). The right half is now empty, and 7 is appended without a comparison. The output is after comparisons. The total is .
Worked example 18.2.7
(One Lomuto partition and the small-n lower bound)
Partition with pivot and . At , so (swap with itself). At , : no change. At , , , swap positions 1 and 2: . At , , , swap positions 2 and 3: . At , , swap positions 3 and 4: . At , , swap positions 4 and 5: . At , : no change. Finally swap positions and 7: . The pivot is at index 5, the left part is not yet sorted internally (the right part happens to be in order), and comparisons were used.
For the lower bound gives since . Merge sort on four keys uses at most comparisons, so no comparison sort can beat it in the worst case.
Worked example 18.2.8
(Quicksort on a sorted input, down to the empty segment)
Take with the last element as pivot. With pivot 4, each of has a key at most 4, so advances every time and each swap is with itself; the final swap is also with itself. The partition returns after 3 comparisons. The left call is on . The right call is on , an empty segment, which returns at once with no comparison.
Pivot 3 on costs 2 comparisons and again leaves an empty right side; pivot 2 on costs 1; the single key costs 0. The total is , as part (a) predicts. Every partition peels off only the pivot, so the recursion has depth and every right call is empty.
Subtle points
Counterexample mode
Quicksort is not stable
Sort by key with the last element as pivot. Both 2s exceed the pivot 1, so the loop never swaps, and the final swap exchanges positions 0 and 2, giving . The two equal keys have been reversed. Merge sort on the same input returns .
Common mistake
(Reading the expected bound as an average over inputs)
The bound is an expectation over the algorithm's own random pivot choices, and it holds for every fixed input. It is not an average over random inputs: a fixed pivot rule has bad inputs, such as sorted input when the last element is the pivot, which costs 10 comparisons for 5 keys.
Common mistake
(Reading the lower bound as a bound for every input)
The statement concerns the worst case over inputs of length . It does not forbid a particular algorithm from sorting particular inputs, such as already sorted ones, faster, and it does not apply to algorithms that inspect keys in ways other than comparing them.
Common mistake
(Using a strict comparison in the merge)
If the merge tests left[i] < right[j] instead of left[i] <= right[j], equal keys are taken from the right side first. For left and right the output is , so a stable sort stops being stable. Sortedness and the number of comparisons are unchanged, which is why this slip is easy to miss.
Exercises with solutions
Quick check
(1. Apply the Lomuto partition to [4,9,1,7,3,8,5] with pivot 5. Give the final array, the pivot index and the number of comparisons.)
Solution · Solution 1
At , , . At , 9 stays. At , , , swap positions 1 and 2: . At , 7 stays. At , , , swap positions 2 and 4: . At , 8 stays. Final swap of positions 3 and 6 gives . The pivot index is 3, and there are 6 comparisons.
Quick check
(2. How many comparisons does quicksort with the last element as pivot make on the sorted array [1,2,3,4,5]?)
Solution · Solution 2
Each partition leaves everything to the left of the pivot, so the sizes of the segments are 5, 4, 3, 2 and 1. The partitions make comparisons, which equals .
Quick check
(3. What is the smallest number of comparisons that a comparison sort must be able to use on some input of 6 distinct keys?)
Solution · Solution 3
It is . Since , at least 10 comparisons are needed on some input.
Quick check
(4. Prove by induction that and give for a power of two.)
Solution · Solution 4
For , the formula gives . Assume it for . Then . Since , we have , the same value. So the formula holds for .
Quick check
(5. Explain why the decision-tree argument needs leaves and not just two outputs for each comparison outcome.)
Solution · Solution 5
Each of the input orderings requires its own rearrangement to be sorted, so two different orderings cannot end at the same leaf. A binary tree with leaves has height at least , so forces height at least , which is .