Efficient comparison sorts
Merge sort, quicksort, and heapsort sort in O(n log n) time. Their different trade-offs explain why real libraries combine them.
Merge sort
Merge sort, described by John von Neumann in 1945, splits the array in half, recursively sorts each half, and merges the two sorted halves by repeatedly taking the smaller front item. The recursion has log2(n) levels, each doing O(n) merging work, so it runs in O(n log n) in every case. It is stable but needs O(n) extra memory for merging arrays.
Merge sort's strengths
Merge sort's guaranteed O(n log n) and stability make it the basis of many library sorts for objects. It is ideal for linked lists, which can be merged without extra arrays, and for external sorting of data too large for memory: sort chunks that fit, write them to disk, then merge the sorted runs.
Quicksort
Quicksort, invented by Tony Hoare around 1959, picks a pivot, partitions the array so smaller items come before it and larger items after, then recursively sorts both sides. Partitioning is O(n) and in place. With balanced splits, the recursion depth is about log2(n), giving O(n log n); it averages about 1.39 n log2(n) comparisons on random input.
Quicksort's worst case
If the pivot is always the smallest or largest item, for example choosing the first element of an already sorted array, each partition removes only one item, giving O(n^2) time and O(n) recursion depth. Choosing a random pivot or the median of three samples makes this extremely unlikely. Recursing on the smaller side first keeps stack space O(log n).
Handling duplicates
Arrays with many equal keys can slow basic quicksort. Three-way partitioning, Dijkstra's Dutch national flag scheme, splits the array into less than, equal to, and greater than the pivot, and recurses only on the outer parts, making arrays with few distinct values sort in near-linear time.
Heapsort and the trade-offs
Heapsort, covered with heaps, guarantees O(n log n) with O(1) extra space but is unstable and has poor cache behaviour. Quicksort is usually fastest in practice thanks to tight, cache-friendly inner loops, but is unstable with a rare quadratic worst case. Merge sort is stable and predictable but uses extra memory.
Hybrid library sorts
Real libraries combine methods. Introsort, used in many C++ std::sort implementations, runs quicksort but switches to heapsort if recursion gets too deep, and uses insertion sort for small pieces. Timsort, designed by Tim Peters in 2002 for Python and also used in Java for objects, finds existing sorted runs, extends short ones with insertion sort, and merges them, so it is stable and very fast on partly sorted real-world data.
Worked example
Partition [7, 2, 9, 4, 3] around pivot 4 (Lomuto style, with the pivot moved to the end): scanning 7, 2, 9, 3, items smaller than 4 are 2 and 3; they are moved to the front, giving [2, 3, 9, 7, 4]; then the pivot swaps into position 2: [2, 3, 4, 7, 9]. The pivot is now in its final position; quicksort recurses on [2, 3] and [7, 9].
Key takeaways
Merge sort (von Neumann, 1945) divides, sorts, and merges in O(n log n) always, stably, but with O(n) extra space; it suits linked lists and external sorting. Quicksort (Hoare, about 1959) partitions around a pivot in place, averaging O(n log n) and running fastest in practice, but worst case O(n^2) unless pivots are randomised or median-of-three. Three-way partitioning handles duplicates. Heapsort guarantees O(n log n) in O(1) space. Introsort and Timsort combine methods for robust, fast library sorts.
Flashcard
Split, sort halves, merge
Check your understanding
Why does quicksort choosing the first element as pivot perform badly on already sorted input?