Insertion sort and selection sort need quadratic time in the worst case. Two classical algorithms reach without extra arrays of size : quicksort, which partitions around a pivot, and heapsort, which turns the array into a binary heap and repeatedly removes the maximum. Merge sort, treated in the unit on selection and linear-time sorting, also achieves and is stable, but it uses a second array. This unit proves the correctness of quicksort and heapsort, derives their costs, and compares the three. It uses the array representation of heaps from the heap unit and the cost vocabulary from the complexity unit.
Quicksort
Quicksort sorts by choosing a pivot, rearranging the segment so that keys at most the pivot come before it and larger keys after it, and recursing on the two sides.
Definition 3.4.1
(Partition around a pivot)
Partitioning around the pivot rearranges the segment and returns an index with such that , every element of is at most , and every element of is greater than . The element at is then in its final sorted position.
int partition(int a[], int lo, int hi) {
int p = a[hi];
int i = lo - 1;
for (int j = lo; j < hi; j++)
if (a[j] <= p) {
i++;
int t = a[i]; a[i] = a[j]; a[j] = t;
}
int t = a[i + 1]; a[i + 1] = a[hi]; a[hi] = t;
return i + 1;
}
void quicksort(int a[], int lo, int hi) {
if (lo < hi) {
int q = partition(a, lo, hi);
quicksort(a, lo, q - 1);
quicksort(a, q + 1, hi);
}
}
Partition invariant. At the start of each iteration for index : every element of is at most , every element of is greater than , and . Initially both regions are empty. If , increasing and swapping with moves to the end of the first region and the displaced larger element to the end of the second; if , the second region simply grows. After the loop the final swap puts at index , with only smaller or equal keys to its left and only larger keys to its right. Partition makes exactly comparisons.
Correctness of quicksort. By strong induction on the segment length. A segment of length 0 or 1 needs nothing. Otherwise the pivot is at its final position, the two recursive segments are strictly shorter, so by hypothesis they are sorted, and they contain precisely the keys that must lie on each side. Hence the whole segment is sorted.
Theorem 3.4.2
(Cost of quicksort)
(a) If every pivot is the minimum or maximum of its segment, quicksort on keys makes comparisons. (b) If each segment is split into parts of sizes and , the comparison count satisfies a recurrence solving to . (c) If the pivot of each segment is chosen uniformly at random and keys are distinct, the expected number of comparisons is at most .
Proof
(Recurrences and the pair-counting argument)
For (a), the recurrence is with , which sums to . With the last element as pivot, an input that is already sorted (or reverse sorted, or consists of equal keys, since the test is ) produces exactly this behavior. For (b), has levels with fewer than comparisons each. For (c), name the keys in sorted order . Two keys are compared at most once, because a comparison involves the current pivot and the pivot is then excluded from further work. Keys and with are compared exactly when the first pivot chosen among is or : choosing some with first separates them for good. All keys are equally likely to be first, so the probability is , and by linearity of expectation
Proof X-ray
Why counting pairs gives the expectation
The key move is to count comparisons by pairs of keys instead of following the recursion tree. Two facts make the pair counts well defined. A pair is compared at most once, since a comparison involves the current pivot and the pivot is then removed from further work, so the number of comparisons is the sum of indicator variables, one per pair. And two keys stay in the same segment until some pivot lies in the closed interval between them, which is why the pair is compared exactly when the first pivot chosen from is an endpoint. Distinctness is used here: with equal keys the sorted order does not exist, and the test sends all copies of the pivot to one side, so the probability is no longer correct. Randomness is used once, to make each of the keys equally likely to be the first pivot among them. The proof closes with linearity of expectation, which needs no independence between different pairs, and with the harmonic bound . Without random pivots, part (a) shows that a fixed rule has an input on which the sum is as large as .
Quicksort is in place apart from recursion depth, which can reach in case (a); recursing on the smaller side first and iterating on the larger bounds the depth by . It is not stable.
Concept lensStructural
The recursion tree is a binary search tree
Record each call that picks a pivot as a node, with the two recursive calls as its left and right subtrees. For distinct keys this tree is a binary search tree on the keys, because the pivot of a call lies between the keys of its two sides. A partition compares every other key of its segment with the pivot, so each key is compared once with each of its proper ancestors, and the total number of comparisons is the sum of the depths of all nodes, the root having depth . For three keys, pivot gives depths with total , and pivot gives a path with depths and total . The best case is a balanced tree and the worst case, part (a), is a path. A uniformly random pivot makes the tree a random binary search tree, and part (c) bounds its expected total depth.
Heapsort
Heapsort uses a max-heap stored in a zero-based array: the children of index are and , and each key is at least its children's keys. (The min-heap of the heap unit would produce descending order with the same method.)
void sift_down(int a[], int i, int size) {
for (;;) {
int big = i, l = 2 * i + 1, r = 2 * i + 2;
if (l < size && a[l] > a[big]) big = l;
if (r < size && a[r] > a[big]) big = r;
if (big == i) return;
int t = a[i]; a[i] = a[big]; a[big] = t;
i = big;
}
}
void heapsort(int a[], int n) {
for (int i = n / 2 - 1; i >= 0; i--)
sift_down(a, i, n);
for (int end = n - 1; end > 0; end--) {
int t = a[0]; a[0] = a[end]; a[end] = t;
sift_down(a, 0, end);
}
}
sift_down(a, i, size) assumes that both subtrees below are already max-heaps within and repairs the heap property at by swapping with the larger child while that child exceeds the key; each swap moves the key one level down, so it takes at most swaps.
Correctness. The first loop processes indices down to 0. Indices from upward are leaves, trivially heaps; by the time index is processed, its children's subtrees are heaps, so sift_down makes the subtree at a heap. After the loop is a max-heap. In the second loop the invariant is: before the iteration with index end, is a max-heap and holds the largest elements in sorted order. The maximum is at ; swapping it to position end extends the sorted suffix, and sift_down repairs the heap on the shorter prefix, because only the root changed.
Cost. The first loop costs by the bottom-up construction argument (most nodes are near the leaves and sink few levels). The second loop runs times with a sift-down of at most levels. Total: in the worst case, in place with extra space. It is not stable.
| Algorithm | Worst-case comparisons | Extra space | Stable |
|---|---|---|---|
| Quicksort | ; expected with random pivot | stack (smaller side first) | no |
| Heapsort | no | ||
| Merge sort (arrays) | yes |
Worked examples
Worked example 3.4.3
(Quicksort on [8, 3, 7, 1, 5, 2])
Partition the whole array with pivot 2 (last element), . Elements 8, 3, 7 are greater than 2. At , , so and we swap positions 0 and 3: . At , 5 is greater. Place the pivot: swap positions and 5: , pivot index 1 (5 comparisons). The left part is trivial. Right part positions 2 to 5, , pivot 3: all of 7, 8, 5 exceed 3, so stays 1; swapping positions 2 and 5 gives , pivot index 2 (3 comparisons). Then positions 3 to 5, , pivot 7: 8 exceeds 7; at , , , swap positions 3 and 4: ; the final swap of positions 4 and 5 gives , pivot index 4 (2 comparisons). The remaining segments and are trivial. The array is sorted after comparisons.
Worked example 3.4.4
(Heapsort on [4, 10, 3, 5, 1])
Build the heap: , so start at . The key 10 at index 1 has children 5 and 1, so nothing moves. At the key 4 has children 10 and 3; swap with 10: , and then 4 at index 1 has children 5 and 1; swap with 5: . This is a max-heap.
Sort phase. Swap positions 0 and 4: ; sift 1 down in a heap of size 4: larger child 5, swap, then at index 1 the child at index 3 is 4, swap: . Swap positions 0 and 3: ; sift down in size 3: larger child 4, swap: . Swap positions 0 and 2: ; sift down in size 2: child 1 is smaller, stay. Swap positions 0 and 1: . The result is .
Worked example 3.4.5
(Expected comparisons for three distinct keys)
Take with keys and a uniformly random pivot at the top level. If the pivot is (probability ), partition makes comparisons and both sides are empty, so the cost is . If the pivot is or (probability ), partition makes comparisons and leaves two keys, which cost one more comparison, so the cost is . The expectation is .
The pair formula gives the same value. The pairs and have , so each is compared with probability ; the pair has , probability . The sum is . The bound holds. For the edge case there are no pairs, the sum is empty and the cost is , as the recursion expects.
Subtle points
Common mistake
(A pivot rule with a bad input family)
Quicksort with the last element as pivot and the test <= degrades to on a sorted array and also on an array of equal keys, where every element goes to the left region and the pivot ends at the last index. A random pivot protects against bad inputs; it does not remove the possibility of bad luck, but makes its probability small. Median-of-three or three-way partitioning handle many equal keys better.
Common mistake
(Heapsort is not stable)
Sort : building the heap compares with and does not swap (not strictly larger), then the first extraction swaps positions 0 and 1 and gives . Equal keys are reversed.
Counterexample mode
Heap construction must run from the last internal node upward
Claim: since sift_down repairs the heap property at one index, calling it for in increasing order also builds a heap. This is false, because sift_down(a, i, size) requires both subtrees below to be heaps already. Take with , so the indices are and . At the subtree rooted at index consists of with child , which is not a heap, so the precondition fails. The call compares the children and , swaps with and gives . Then swaps with its child and gives . The root is smaller than its child , so this is not a max-heap, and the sort phase would then extract the wrong maximum. In the correct order, first gives , and then swaps with and then with , giving the heap . The repair is the downward loop of the build phase, which guarantees that the children's subtrees are heaps before each call.
Exercises with solutions
Quick check
(1. Apply partition to [6,2,9,4,7,1,5] with pivot 5 (last element). Give the resulting array, the pivot index and the number of comparisons.)
Solution · Solution 1
: . : , , swap positions 0 and 1: . : . : , , swap positions 1 and 3: . : . : , , swap positions 2 and 5: . Final swap of positions 3 and 6: . The pivot index is 3 and there are 6 comparisons.
Quick check
(2. How many comparisons does this quicksort make on four equal keys [7,7,7,7]?)
Solution · Solution 2
Every element satisfies , so advances each time and the pivot ends at the last index. Segment sizes are 4, 3, 2, 1, so the comparisons are , the worst case for .
Quick check
(3. Build a max-heap from [2,9,7,6,5,8] with the heapsort build loop and give the array.)
Solution · Solution 3
, start at . Key 7 has only the child at index 5 (key 8): swap, giving . At : key 9 has children 6 and 5, no change. At : key 2 has children 9 and 8; swap with 9: ; at index 1, key 2 has children 6 and 5; swap with 6: . At index 3 there are no children. The heap is .
Quick check
(4. Perform the first extraction step of the sort phase on the heap [9,6,8,2,5,7] and give the array and the heap size afterwards.)
Solution · Solution 4
Swap positions 0 and 5: . The heap now occupies indices 0 to 4. Sift 7 down: children 6 and 8, the larger is 8, so swap: . Index 2 has children at indices 5 and 6, outside the heap of size 5, so stop. The array is and the heap size is 5.
Quick check
(5. Why does the build phase of heapsort cost only although it calls sift-down about times?)
Solution · Solution 5
A call at a node of height costs at most swaps. A heap on nodes has at most nodes of height , so the total is at most , because . Hence the build phase takes , not .