Merge Sort and Quicksort
Two divide-and-conquer sorts and the recurrences that time them.
The idea
Merge sort and quicksort both put $n$ items into sorted order by divide and conquer: split the array in two, sort each part recursively, put the parts together. They differ in which of those steps carries the work, and that difference sets their costs.
Algorithm.
Algorithm: Merge Sort Input: an array A of n items Output: the same items in sorted order 1. if A has at most one item, return it // already sorted 2. cut A at its midpoint into a left half and a right half 3. sort each half by running these same steps on it 4. merge the sorted halves: repeatedly move the smaller of their two front items to the output when one half runs out, append the rest of the other 5. return the merged array
The split is trivial and the merge is the real work, costing $\Theta(n)$ time. Because the cut is always even, the recursion is $\log_{2} n$ levels deep and each level merges $n$ items in total (a cost $cn$ for some constant $c$), so merge sort runs in $\Theta(n \log n)$ time on every input. It requires $\Theta(n)$ extra space to merge into.
Algorithm.
Algorithm: Quicksort Input: an array A of n items Output: the same items in sorted order 1. if A has at most one item, return it 2. choose an item of A as the pivot p 3. partition: rearrange A so every item smaller than p precedes it and every larger item follows it // p now sits in its final position 4. sort the part before p and the part after p by running these same steps on each 5. return the array // with p between the sorted parts, the whole array is sorted
Here the split carries the work: partitioning costs $\Theta(n)$ time, and nothing remains to combine. Quicksort sorts in place, but the quality of its split depends on where the pivot lands. A pivot near the median gives $\log n$ levels and $\Theta(n \log n)$ time; a pivot at an extreme peels off one element per level, giving $n$ levels of linear work and $\Theta(n^{2})$. Choosing the pivot at random makes the bad case unlikely, and the expected time is $\Theta(n \log n)$.
Ways to work on it
- Walkthrough. Merge sort's recurrence, recursion tree, and the n n bound.
- Practice. Classify the running time of a merge sort or quicksort scenario.
- Hardest. Derive and solve quicksort's worst-case recurrence.
Not sure where to start? Take the ten-question placement test.