TwiddleLab / Code / Algorithms in Motion
Merge Sort: Merge, Then Merge Again
What you will learn
- Merge sort: one card is already sorted. Merge pairs, then fours, then eights, until one pile is left.
- There are log₂ n rounds, and each round moves every card once: about n log n steps.
- For a million items: about 20 million steps, against about 500 billion for selection sort.
How the lesson goes
Selection sort on a million items: about 500 billion comparisons. Can merging do better?
Merge sort only ever merges. Bet how many steps it needs for a million.
Deal yourself 8 cards, then cut them down to single cards.
Pick any 8. Then tap a pile to cut it in half, until every pile is one card.
Now merge your hand back. The machine does pairs and fours; you do the last round.
Drag the smaller top card, like last lesson.
16 cards. Count the rounds and the work in each.
Press Merge round until one pile is left.
Merge sort.
Merge sort: start with piles of one card. Merge neighbours into twos, then fours, then eights, until one pile is left.
The number of rounds is log₂ n: how many times n halves down to 1. Each round moves every card once: n work.
Total: about n log n. A million items: 20 rounds of a million, about 20 million steps.
How many cards make a 10-level tower?
Each floor is one round of merging. Find the size, then Check.
Each round halves the number of piles. Starting from 1024 piles of one, it takes 10 halvings to reach 1 pile.
Show the list after 2 rounds of merge sort.
Each group of 4 is sorted inside. Drag bars to swap them, then Check.
After round k, every group of 2ᵏ neighbours is sorted inside, but the groups haven't met yet.
1 048 576 items. Which plan finishes within a minute?
A million steps a second. Tap a plan, then Check.
n log₂ n = 1 048 576 x 20 ≈ 21 million. n² = 1 048 576² ≈ 1.1 trillion. At a million a second: 21 s against about 12.7 days.
Beat the spotlight.
32 cards. Selection sort starts when you do. Press Merge round 5 times, fast.
Previous lesson: Merging Sorted Piles · Next lesson: Quicksort: Pick a Pivot · Part of the course: Algorithms in Motion
Lessons are interactive and need JavaScript. Turn it on to play them.
