Overview
Merge Sort is a stable divide-and-conquer algorithm that splits the array into halves, sorts each half recursively, and then merges the two sorted halves into one. It guarantees O(n log n) time regardless of the input.
How Merge Sort works
- Divide the array into two halves at the midpoint.
- Recursively sort the left half and the right half.
- Merge the two sorted halves by repeatedly taking the smaller front element.
- The merge of the top-level halves yields the fully sorted array.
When to use it
- When a guaranteed O(n log n) worst case is required.
- When stability matters (e.g. sorting records by a secondary key).
- External sorting of data too large for memory, and sorting linked lists.
Complexity analysis
The array splits into log n levels, and each level does O(n) work to merge, giving O(n log n) in every case. The trade-off is O(n) auxiliary memory for the merge buffer. Merge Sort is stable.
Frequently asked questions
Why does Merge Sort need extra memory?
Merging two sorted halves in place is hard to do efficiently, so the standard version copies elements into a temporary buffer of size O(n) while merging.
Is Merge Sort always O(n log n)?
Yes — the recursion depth and per-level merge cost do not depend on the input order, so best, average, and worst cases are all O(n log n).