Merge Sort
Merge two sorted runs by always taking the smaller front value.
Decision · step 4 of 36Merge Sort: Eight values
1 is smaller than 5, so 1 is written to index 0.
What you will see
MERGE neighbouring runs -> the smaller head is written down -> runs double in width each pass.
Cost
| Best | O(n log n) |
|---|---|
| Average | O(n log n) |
| Worst | O(n log n) |
| Space | O(n) |
Properties
- ✓ comparison based
- ✓ stable
- × in place
- × adaptive
- × online
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next, compare two runs.
Screen readers: Cells announce index, value and state (comparing, swapped, sorted); each step announces the comparison outcome and any move.
Reduced motion: Swaps become value crossfades with outline flashes; sorted-region growth is a static span change.
Before this
Leads to
Topics that need this one first.