← Knowledgebase

Merge sort: merging sorted runs

The idea

Merge sort is divide and conquer, like quicksort, but it does the work at the other end. Split the array in half, sort each half (the same way), then merge the two sorted halves into one. Splitting continues until each piece holds a single value, which is trivially sorted. So everything happens in the merges.

Merging two sorted runs

  1. Point i at the front of the left run and j at the front of the right run.
  2. Compare the two fronts. Copy the smaller into a buffer and move that run's pointer on.
  3. When one run is used up, copy the rest of the other run as is: it's already sorted.
  4. Copy the buffer back into the array.

Why only the fronts? Each run is sorted, so its front is its smallest remaining value. The smallest value overall must be one of the two fronts.

low left run high right run merged in the buffer so far · not part of this merge

Cost

Merge sort
TimeO(n log n) always: halving gives about log n levels, and each level's merges touch all n values once.
Extra spaceO(n) for the buffer: the price of guaranteed speed.
Stable?Yes, if ties take from the left run first. That's why many libraries use merge sort variants (Timsort) for sorting records.

Compared with quicksort (in place, usually faster, but O(n²) in the worst case) and heapsort (in place, O(n log n), not stable), merge sort trades memory for predictability and stability.