Merge sort
Overview
Merge sort divides a range in half, sorts each half, and merges the two sorted halves into a single ordered sequence. When combining two stacks of invoices already ordered by date, you only need to compare the top invoice of each stack to pick the next earliest date; you never have to rescan the remaining piles.
History
John von Neumann devised merge sort in 1945 in a handwritten manuscript preparing an internal sorting program for the EDVAC. In his 1970 article “Von Neumann’s First Computer Program,” Donald Knuth analyzed the manuscript’s merge routine and instruction layout for building longer sorted strings from shorter ones.1 Herman H. Goldstine and von Neumann subsequently published the flowcharts and inductive correctness argument in their 1948 report *Planning and Coding of Problems for an Electronic Computing Instrument*.2
Splitting and stable merging
A subrange of length 0 or 1 is already sorted. To sort , split it at into and , sort both halves recursively, and merge them by comparing their front elements into a scratch buffer. The comparison count satisfies the classic divide-and-conquer recurrence:
A sort is stable when records with equal keys keep their original relative order. Because every element in the left half appeared before every element in in the input, choosing the left element whenever keys tie () preserves stability. Replacing <= 0 with < 0 would let right-half ties jump ahead and make the sort unstable.
Executable example
Sorting bare numbers hides whether equal keys swapped places. Below, four records carry both a numeric key and a distinct id. The comparator compare(a, b) must define a consistent total preorder—returning a negative number, zero, or a positive number according to whether a precedes, ties with, or follows b.
function mergeSort<T>(input: readonly T[], compare: (a: T, b: T) => number): T[] {
const values = [...input];
const buffer = new Array<T>(values.length);
function sort(lo: number, hi: number): void {
if (hi - lo <= 1) return;
const mid = lo + Math.floor((hi - lo) / 2);
sort(lo, mid);
sort(mid, hi);
let left = lo;
let right = mid;
for (let out = lo; out < hi; out++) {
// Taking the left element on a tie (compare <= 0) preserves stability.
if (left < mid && (right >= hi || compare(values[left]!, values[right]!) <= 0)) {
buffer[out] = values[left++]!;
} else {
buffer[out] = values[right++]!;
}
}
for (let i = lo; i < hi; i++) values[i] = buffer[i]!;
}
sort(0, values.length);
return values;
}
const records = [
{ key: 2, id: 'A' }, { key: 1, id: 'B' },
{ key: 2, id: 'C' }, { key: 1, id: 'D' },
];
const result = mergeSort(records, (a, b) => a.key - b.key);
console.log(result.map(item => item.id).join(','));
console.log(records.map(item => item.id).join(','));B,D,A,C
A,B,C,DRecords B and D (key 1) come first with B still ahead of D, followed by A and C (key 2) in their original order. Allocating a single scratch buffer up front avoids allocating and garbage-collecting temporary arrays at every recursive call.
Cost and practical boundaries
Assuming comparisons, merge sort runs in time in the best, average, and worst cases: recursion levels each merge elements in linear time. Auxiliary space is for the scratch buffer plus for the call stack.
Unlike quicksort, merge sort never degrades to on adversarial inputs and guarantees stability, at the price of extra array space. On linked lists, however, merging relinks pointers in place using auxiliary space, and sequential access makes multi-way merge sort the standard choice for external sorting on disk. For partially ordered real-world arrays, adaptive variants such as Timsort (used in Python, Java, and V8) exploit existing natural runs to reach time on nearly sorted inputs.
See also
Footnotes
- Donald E. Knuth, “Von Neumann’s First Computer Program,” ACM Computing Surveys 2(4), 1970, pp.247–260, especially p.253, “The Sorting Program”. Paper scan, DOI. ↩
- Herman H. Goldstine, John von Neumann, Planning and Coding of Problems for an Electronic Computing Instrument, Part II, Vol. 2, Institute for Advanced Study, 1948, §7.6–7.8. ↩