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 running time 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
C++20
The C++20 version also preserves input order among records with equal keys. Its comparator returns a negative number, zero, or a positive number for before, equal, or after. Copyable records go into a by-value working array and a reused buffer, leaving the caller’s input unchanged.
#include <cstddef>
#include <iostream>
#include <vector>
template<class T, class Compare>
void sortRange(std::vector<T>& values, std::vector<T>& buffer,
std::size_t lo, std::size_t hi, Compare compare) {
if (hi - lo <= 1) return;
const auto mid = lo + (hi - lo) / 2;
sortRange(values, buffer, lo, mid, compare);
sortRange(values, buffer, mid, hi, compare);
auto left = lo;
auto right = mid;
for (auto out = lo; out < hi; ++out) {
// Choose the left item on a tie to retain the input order of equal keys.
if (left < mid && (right == hi || compare(values[left], values[right]) <= 0)) {
buffer[out] = values[left++];
} else {
buffer[out] = values[right++];
}
}
for (auto i = lo; i < hi; ++i) values[i] = buffer[i];
}
template<class T, class Compare>
std::vector<T> mergeSort(std::vector<T> values, Compare compare) {
// A by-value working array and a copied buffer leave the caller’s array unchanged.
auto buffer = values;
sortRange(values, buffer, 0, values.size(), compare);
return values;
}
struct Record { int key; char id; };
int main() {
const std::vector<Record> records{{2, 'A'}, {1, 'B'}, {2, 'C'}, {1, 'D'}};
const auto result = mergeSort(records, [](const Record& a, const Record& b) {
return (a.key > b.key) - (a.key < b.key);
});
for (std::size_t i = 0; i < result.size(); ++i) {
if (i != 0) std::cout << ',';
std::cout << result[i].id;
}
std::cout << '\n';
for (std::size_t i = 0; i < records.size(); ++i) {
if (i != 0) std::cout << ',';
std::cout << records[i].id;
}
std::cout << '\n';
return 0;
}B,D,A,C
A,B,C,DTypeScript
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++) {
// Take the left item when it comes first or ties; ties retain their input order.
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: there are recursion levels, with a total of work per level. 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. Adaptive merge sorts such as Timsort reuse existing sorted runs and take time on sorted input. Java distinguishes object-array and primitive-array sorting implementations. Current CPython and V8 main sources describe Powersort merge scheduling, so the relevant API and version identify the implementation more precisely than a language-wide algorithm label.3
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. II, Institute for Advanced Study, 1948-04-15, §11.3–11.4. IAS original. ↩
- Oracle Java SE 25, Arrays: object sort and primitive sort implementation notes. API. CPython listsort.txt; V8 array-sort.tq. Main-source observations checked 2026-11-07. ↩