About Merge Sort
Merge Sort divides the array into halves recursively until each sub-array has one element, then merges them back in sorted order. It guarantees O(n log n) time in all cases but requires O(n) extra space for the merge buffer.
Complexity Analysis
- Time Complexity
- O(n log n)
- Space Complexity
- O(n)
- Difficulty
- intermediate
Key Concepts
Divide and Conquer
Merge Sort divides the problem into smaller sub-problems (halving), solves them, and combines (merges) the results.
Stability
When equal elements appear, we always take from the left half first, preserving their original relative order.
Guaranteed O(n log n)
Unlike QuickSort, Merge Sort always runs in O(n log n) regardless of input order. The trade-off is O(n) extra space.
Auxiliary Space
The merge step requires a temporary buffer of size n. This is the main disadvantage compared to in-place sorting algorithms.
Common Pitfalls
Forgetting to copy back
After merging into the auxiliary buffer, the values must be copied back into the main array. Forgetting this means subsequent merges operate on stale data.
Off-by-one in merge boundaries
The mid index belongs to the LEFT sub-array [left..mid], and the right starts at mid+1. Getting this wrong duplicates or skips elements.