Divide & conquer · Intermediate
Merge Sort
Split into smaller lists, sort them recursively, then merge the ordered halves.
- Best
- O(n log n)
- Average
- O(n log n)
- Worst
- O(n log n)
- Space
- O(n)
- Stability
- Stable
- Memory model
- Uses auxiliary storage
How it builds order
- Split until every range has one item.
- Compare the front items of two neighboring runs.
- Write the smaller one into a temporary buffer.
- Copy the merged run back.
Why it works
Single-item lists are sorted. Merging two sorted lists by choosing the smaller front always produces another sorted list.
Watch for: The merge buffer is extra memory that turns two sorted halves into one sorted range.
The interactive version of this page adds the full trace, synchronized pseudocode, practice decisions, input experiments, and mastery review.