merge sort

A divide-and-conquer sort that splits the list in half, sorts each half recursively and then merges the two sorted halves.

In more detail

Its recurrence T(n) = 2T(n/2) + n gives O(n log n) in every case, not just on average. It is stable but needs O(n) extra memory for merging. The merge step, repeatedly taking the smaller front item of two sorted lists, is also the heart of external sorting.

Related terms

Taught in

References