What Is Merge Sort?
Merge Sort is a divide-and-conquer algorithm that keeps splitting the array in half until pieces can't be split further, then merges sorted pieces back together on the way up. Splitting is easy; the real work is in merging.
The one-line idea: "merging two already-sorted arrays is fast." If both pieces are sorted, you can combine them in O(n) by repeatedly taking the smaller front element.
The Heart Is Merging
Say you merge two sorted arrays A and B.
1. Keep a pointer at the front of A and of B.
2. Take the smaller of the two pointed-to values into the result, and advance only that pointer.
3. When one side empties, append the rest of the other side as is.
Each element is looked at exactly once, so merging is O(n). Repeating that merge across depth log n gives O(n log n) overall.
How It Works
Step 1. Split the range [lo, hi] at its middle mid into left [lo, mid] and right [mid+1, hi].
Step 2. Recursively sort the left and right halves. A range of size 1 is already sorted, so stop there (base case).
Step 3. Merge the two sorted ranges into one sorted range using the procedure above.
Step 4. As recursion unwinds, ever-larger ranges merge, until the whole array is sorted.
"Splitting" and "merging" are distinct actions, and the AlgoNote visualization separates the split steps from the merge steps.
Time and Space Complexity
| Complexity | |
|---|---|
| Time | O(n log n) |
| Space | O(n) |
Split depth is always log n and each level's merge is O(n), so it guarantees O(n log n) no matter the input (unlike quick sort, there is no bad case). The cost is a temporary array for merging, making space O(n).
Walking Through an Example
Sort [5, 2, 8, 1].
- •Split:
[5, 2]and[8, 1] - •Sort each:
[2, 5]and[1, 8] - •Merge: 2 vs 1 → 1, 2 vs 8 → 2, 5 vs 8 → 5, leftover 8 →
[1, 2, 5, 8]
Small sorted pieces combine into the finished whole.
Common Mistakes
- •Temp array: forgetting to copy the merged result from the temp array back into the original overwrites values.
- •Keeping stability: on ties, take the left (earlier) piece's value first to stay stable (preserve original order of equal keys).
- •Computing mid:
(lo + hi) / 2can overflow for large numbers →lo + (hi - lo) / 2is safe.
See It in Action on AlgoNote
Watch how the array splits in half and how two sorted pieces merge smallest-first, step by step on AlgoNote.