01Overview
In 1945 von Neumann wrote down merge sort; in 1960 Hoare proposed quicksort. Quicksort is O(n log n) on average but O(n²) in the worst case, which is why random pivots and median-of-three became standard tricks. In 1964 heapsort pushed the worst case down to O(n log n) as well.
Comparison sorting has a lower bound of Ω(n log n); to go faster you must exploit the data itself. Counting, radix and bucket sorts finish in linear time on integers or on a uniform distribution. Real sorting must also weigh caches, stability and partially sorted input — Timsort is exactly that combination of engineering concerns, and Python and Java both adopted it.
02History
- 1945
Merge sort
von Neumann implements it on the EDVAC.
- 1960
Quicksort
Hoare's in-place divide and conquer.
- 1964
Heapsort
Williams gives an in-place algorithm with worst-case O(n log n).
- 2002
Timsort
An adaptive merge sort designed for real-world data.
03Core concepts
Divide and conquer
Split the problem into subproblems, solve recursively, then merge.
Comparison lower bound
A comparison sort needs at least Ω(n log n) comparisons.
Stability
Equal elements keep their relative order after sorting.
04Hands-on
Do it once — it beats reading it ten times
Implement three-way quicksort and compare it with the built-in sort on data with many duplicate keys
05Self-check
Say it in your own words first, then open the answer. Whatever you cannot explain is what to review next.
Can you explain "Divide and conquer"?
Split the problem into subproblems, solve recursively, then merge.
Can you explain "Comparison lower bound"?
A comparison sort needs at least Ω(n log n) comparisons.
Can you explain "Stability"?
Equal elements keep their relative order after sorting.
What problem did it solve, and why was there nothing better at the time?
Go back to the history section: how was this done before, and what did it cost?
If you had to build it today, how would you break it down?
Use the hands-on task above: write a plan of at most three steps before you start.
06Key people
Tony Hoare
1934 –
Quicksort and Hoare logic.
John von Neumann
1903 – 1957
Merge sort and the stored-program computer.
07Further reading
- Introduction to Algorithms, Part II
- Programming Pearls