Sorting by splitting
How to put a huge pile of things in order, by splitting it up first.
What you are looking at
The dots start in a mixed-up order and end up in a neat grid. The sorting happens in rounds, with groups merging into bigger and bigger sorted groups.
The idea
Say you have a big pile of numbered cards, all mixed up. You could look for the smallest card, set it aside, then look for the next smallest, and so on. That works, but with a thousand cards it takes forever.
Here is a faster way. Split the pile in half. Split each half in half. Keep going until every pile has one card. One card is already in order. Now merge: take two piles, and always take the smaller of the two top cards. That makes a sorted pile of two. Merge those into piles of four, then eight, and so on, until all the cards are in one sorted pile.
The trick is that merging two sorted piles is easy and quick. The splitting does not cost anything. So the hard problem turns into a lot of easy ones.
Where else you see it
- Sorting a deck of cards or a stack of papers into alphabetical order with a friend.
- Your phone sorting your contacts or photos.
- Any big database sorting its records.
Go deeper: the proper names and the math
This is merge sort, a divide-and-conquer algorithm. It splits the list log₂ n times, and each level of merging does about n comparisons, so the total is O(n log n). The recurrence is T(n) = 2T(n/2) + n.
Comparison-based sorting cannot do better than log₂(n!) ≈ n log₂ n comparisons in the worst case. For a million items, n log n is about 20 million steps, while checking every pair (n²) is about a trillion. Merge sort needs extra memory to merge, which is its main cost.