Merge Sort

Merge Sort

Merge sort is a stable divide and conquer sort with guaranteed linearithmic time. It splits the array in half, recursively sorts each half, then merges the two sorted halves into one.

The merge step

Merging takes two already sorted lists and weaves them together. Keep an index into each list and repeatedly copy the smaller front element into the output, advancing that index. When one list empties, append the rest of the other. Merging two halves is linear in their combined length.

Why it is reliable

Because the array always splits evenly, merge sort runs in linearithmic time on every input, with no bad case like quicksort has. It is also stable, meaning equal elements keep their original order, which matters when sorting records by multiple keys.

The tradeoff is memory: the standard merge needs extra space to hold the merged output, so it is not in place. This makes it a strong choice for sorting linked lists and for external sorting of data too large for memory.

Key idea

Merge sort splits, sorts, and merges to guarantee linearithmic, stable sorting at the cost of extra memory.