Handshakes with a plan
O(n log n) — The Sorting Floor
The analogy
You cannot sort a pile without looking at every item (that is the n), and the smartest arrangements halve the problem as they go (that is the log n). Together they are the realistic best for general sorting — much closer to a line than to a curve.
Visualizer
Levels times width
step 1 / 5| level 1 | · | · | · | · | · | · | · | · |
| level 2 | · | · | · | · | · | · | · | · |
| level 3 | · | · | · | · | · | · | · | · |
Sorting 8 items by splitting. How many times can you halve 8 before you reach single items?n = 8
import math n = 8 math.log2(n) # 3 levels of splitting n * math.log2(n) # 24 units of work sorted(a) # Timsort: O(n log n) heapq.heapify(a) # O(n), then log n per pop
Check yourself
The best possible comparison sort is…