Merge sort
Merge sort splits the array in half recursively until each piece holds at most one value, then merges pairs of sorted halves back together by repeatedly taking the smaller of the two next unmerged values.
When it is the right choice
Merge sort is the right choice when predictable O(n log n) performance matters more than memory use, and when stability is required — for instance sorting records by a secondary key after already sorting them by a primary one. Its downside is that merging needs O(n) auxiliary space, unlike quicksort's in-place partitioning, so it is a weaker choice under tight memory constraints.
How it works
- If the current range holds more than one value, split it at the middle into a left half and a right half.
- Recursively sort the left half.
- Recursively sort the right half.
- Merge the two sorted halves by repeatedly comparing their next unmerged values and writing the smaller one into the array.
- Once one half is exhausted, copy the remaining values from the other half back into the array.
Worth noticing
- Its O(n log n) performance is the same in the best, average and worst case — unlike quicksort, it has no input that makes it degrade.
- It needs O(n) extra space for the merge buffers — watch the buffer track beneath the array fill up during each merge to see exactly where that space goes.
- It is stable, provided the merge step takes the left value whenever the two compared values are equal, as it does here.
Cost
- Best
- O(n log n)
- Average
- O(n log n)
- Worst
- O(n log n)
- Extra space
- O(n)
- Stable
- Yes