Meet sorting
Why sorting matters, what makes one algorithm better, and a playground with all five. · 6 min read
Sorting — arranging items into order — is one of the most studied problems in computing, and a perfect first algorithm to see. The same input can be sorted by very different strategies, and watching them side by side makes their personalities obvious.
Press play below, then switch algorithms and watch how each one moves elements around. Drag the timeline to scrub backwards — every step is recorded, so you can rewind any moment.
Interactive visualization: Sorting playground — step through it frame by frame on this page.
What makes one better?
Three things separate sorting algorithms:
- Time complexity — how many comparisons and swaps as the array grows. The counters under the visualizer make this tangible.
- Space — does it sort in place (
O(1)extra) or need a copy (O(n))? - Stability — does it keep equal elements in their original relative order? Matters when you sort by one key after another.
Why comparison sorting bottoms out at n log n
If a sorting algorithm only learns by comparing pairs of elements, it must distinguish all n! possible input orders. A comparison has two outcomes, so after h comparisons a decision tree has at most 2ʰ leaves.
need at least n! leaves— Each possible ordering must end at a different sorted answer.2ʰ ≥ n!— A binary comparison tree of height h has at most 2ʰ leaves.h ≥ log₂(n!)— Solve for the minimum number of comparisons.log₂(n!) = Θ(n log n)— By Stirling's approximation / summing logs.
Result: Ω(n log n) lower bound