Merge Sort

in progressThis lesson is still being built - content, demos, and checkpoints may change before release.

Merge sort

Loading interactive demo…

Merge sort splits the array in half, sorts each half recursively, then merges the two sorted halves by repeatedly taking the smaller front bar. The left half is copied to a buffer first; translucent bars are those copies waiting to be written back. Take the tour, or press and explore. Legend:

The panel beside the stage is the real MergeSort class from the published library executing in your browser, with the current line highlighted.

The left run's front bar - in its own slot before anything is displaced, then as a held copy (always the brightest bar).
The right run's front bar. The bracket joins the two fronts; the smaller one is written next.
The left run of the merge in progress.
The right run of the merge in progress. Both runs are already sorted; merging is the whole job.
The part of the range already written back in order.
Every bar, once the whole array is sorted.

Halving gives log n levels and each level writes at most n bars, so merge sort is O(n log n) on every input, and ties go to the left run, so equal values keep their order: the sort is stable. The price is the buffer: it is not in place.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

Halving the range gives a recursion $\lceil \log_2 n \rceil$ levels deep, and every level merges runs whose lengths add up to at most $n$ . Merging two runs of total length $m$ takes at most $m$ writes and at most $m - 1$ comparisons, so

T(n) = 2\,T(n/2) + O(n) = O(n \log n)

on every input: best, average and worst case all cost $\Theta(n \log n)$ , and the merge count is always exactly $n - 1$ . Only the comparison count moves with the data, between about $(n/2) \log_2 n$ for input that is already in order and $n \lceil \log_2 n \rceil$ at most. Ties go to the left run, so equal keys keep their original order: the sort is stable. The price is space. The merge needs a buffer for the left run, so this implementation uses $O(n)$ extra memory and is not in place; that buffer is the one real difference from heapsort, which is also $O(n \log n)$ but neither stable nor buffered.

Choices worth reading closely in the implementation (the code panel's comments and tracer checkboxes reveal the full published file):

Ranges are half-open, a[lo, hi): hi - lo is the length, the base case is a range shorter than two, and mid is computed as lo + Math.floor((hi - lo) / 2), so there is no + 1 or - 1 anywhere to get wrong.
Only the left run is copied: buf = a.slice(lo, mid). The right run is read in place, because the write cursor k can never overtake j; the right run's unread part is always ahead of it.
left <= right, not <: on a tie the left run wins, and that single character is what makes the sort stable.
When the right run is used up, right becomes Infinity, so the same comparison drains the buffer without a second loop, and the trace shows those final writes without a compare.
The loop stops when the buffer is empty. Whatever remains of the right run is already sitting in its final slots, which is why a merge can finish with fewer writes than bars.
sort copies the input once and never touches the caller's array; the recursion works on that copy.

Merge sort is among the first algorithms ever written for a stored-program computer: John von Neumann drafted a merge sort routine in 1945 for the planned EDVAC, and a detailed bottom-up version appears in the 1948 Goldstine and von Neumann reports on planning and coding. Merging suited the machines of the day, which read forward-only tape, and it still anchors the stable sorts in Python, Java and JavaScript engines today.

1945John von Neumann - Writes a merge sort routine for the EDVAC, the stored-program machine his First Draft report describes, before the machine exists.source
1948Herman Goldstine and John von Neumann - Planning and Coding of Problems for an Electronic Computing Instrument gives a detailed description and analysis of bottom-up merge sort.source
1970Donald Knuth - Von Neumann's First Computer Program, in ACM Computing Surveys, reads and critiques the 1945 sorting routine line by line.source
1973Donald Knuth - The Art of Computer Programming Vol. 3, Sorting and Searching, analyzes sorting by merging alongside every other method of its day.source
2002Tim Peters - Timsort, a merge sort that exploits runs already present in the data, becomes Python's standard sort in version 2.3.source

Used today

Stable library sorts - Python's sorted, Java's object sort and V8's Array.prototype.sort are all merge sorts (Timsort), because merging keeps equal keys in order.
External sorting - Data too big for memory is sorted as runs on disk or tape and merged in sequential passes; the classic tape-drive sort is a merge.
Linked lists - Merging needs no random access, so the Linux kernel's list_sort is a stable, non-recursive merge sort over linked lists.

n16

comparisons: 0
writes: 0
merges: 0

merge-sort.ts

import type { Tracer } from "../trace";import type { SortAlgorithm } from "./sort-algorithm";/** * Top-down merge sort: split the range in half, sort each half * recursively, then merge the two sorted halves by repeatedly taking * the smaller front element. Only the left half is copied to a buffer: * the right half is read in place, because a write can never overtake * the right run's unread part. * * Time: O(n log n) always. Space: O(n) extra for the merge buffer. */export class MergeSort implements SortAlgorithm {  readonly name = "merge-sort";  constructor(private readonly tracer?: Tracer) {}  sort(input: readonly number[]): number[] {    const a = [...input];    const array = [...input];    this.sortRange(a, 0, a.length);    this.sortRange(array, 0, array.length);    return a;    return array;  }  /** Sort the half-open range a[lo, hi). */  private sortRange(a: number[], lo: number, hi: number): void {  private sortRange(array: number[], low: number, high: number): void {    if (hi - lo < 2) return;    if (high - low < 2) return;    const mid = lo + Math.floor((hi - lo) / 2);    const middle = low + Math.floor((high - low) / 2);    // ▸ cut the range in half and sort each half first    this.tracer?.emit("split", { lo, mid, hi, array: [...a] });    this.tracer?.emit("split", { low, middle, high, array: [...array] });    this.sortRange(a, lo, mid);    this.sortRange(array, low, middle);    this.sortRange(a, mid, hi);    this.sortRange(array, middle, high);    this.merge(a, lo, mid, hi);    this.merge(array, low, middle, high);  }  /** Merge the sorted runs a[lo, mid) and a[mid, hi) back into a[lo, hi). */  private merge(a: number[], lo: number, mid: number, hi: number): void {  private merge(array: number[], low: number, middle: number, high: number): void {    const buf = a.slice(lo, mid);    const leftCopy = array.slice(low, middle);    // ▸ copy the left run aside, then merge the two runs    this.tracer?.emit("merge", { lo, mid, hi, array: [...a] });    this.tracer?.emit("merge", { low, middle, high, array: [...array] });    let i = lo; // next element of the left run (read from buf)    let nextLeft = low; // next element of the left run (read from buf)    let j = mid; // next element of the right run (read in place)    let nextRight = middle; // next element of the right run (read in place)    for (let k = lo; i < mid; k++) {    for (let target = low; nextLeft < middle; target++) {      const left = buf[i - lo]!;      const left = leftCopy[nextLeft - low]!;      const right = j < hi ? a[j]! : Infinity; // a used-up right run never wins      const right = nextRight < high ? array[nextRight]! : Infinity; // a used-up right run never wins      // ▸ which front bar is smaller, left copy or right run      if (j < hi) this.tracer?.emit("compare", { lo, hi, i, j, left, right, array: [...a] });      if (nextRight < high) this.tracer?.emit("compare", { low, high, nextLeft, nextRight, left, right, array: [...array] });      const fromLeft = left <= right; // ties go left: the sort stays stable      // ▸ write the smaller one into the next slot      this.tracer?.emit("write", { lo, hi, from: fromLeft ? i : j, to: k, array: [...a] });      this.tracer?.emit("write", { low, high, from: fromLeft ? nextLeft : nextRight, to: target, array: [...array] });      a[k] = fromLeft ? left : right;      array[target] = fromLeft ? left : right;      if (fromLeft) i++;      if (fromLeft) nextLeft++;      else j++;      else nextRight++;    }  }}

The array before sorting - merge sort will halve it until every run is a single bar.

import type { Tracer } from "../trace";import type { SortAlgorithm } from "./sort-algorithm";/** * Top-down merge sort: split the range in half, sort each half * recursively, then merge the two sorted halves by repeatedly taking * the smaller front element. Only the left half is copied to a buffer: * the right half is read in place, because a write can never overtake * the right run's unread part. * * Time: O(n log n) always. Space: O(n) extra for the merge buffer. */export class MergeSort implements SortAlgorithm { readonly name = "merge-sort"; constructor(private readonly tracer?: Tracer) {} sort(input: readonly number[]): number[] { const a = [...input]; const array = [...input]; this.sortRange(a, 0, a.length); this.sortRange(array, 0, array.length); return a; return array; } /** Sort the half-open range a[lo, hi). */ private sortRange(a: number[], lo: number, hi: number): void { private sortRange(array: number[], low: number, high: number): void { if (hi - lo < 2) return; if (high - low < 2) return; const mid = lo + Math.floor((hi - lo) / 2); const middle = low + Math.floor((high - low) / 2); // ▸ cut the range in half and sort each half first this.tracer?.emit("split", { lo, mid, hi, array: [...a] }); this.tracer?.emit("split", { low, middle, high, array: [...array] }); this.sortRange(a, lo, mid); this.sortRange(array, low, middle); this.sortRange(a, mid, hi); this.sortRange(array, middle, high); this.merge(a, lo, mid, hi); this.merge(array, low, middle, high); } /** Merge the sorted runs a[lo, mid) and a[mid, hi) back into a[lo, hi). */ private merge(a: number[], lo: number, mid: number, hi: number): void { private merge(array: number[], low: number, middle: number, high: number): void { const buf = a.slice(lo, mid); const leftCopy = array.slice(low, middle); // ▸ copy the left run aside, then merge the two runs this.tracer?.emit("merge", { lo, mid, hi, array: [...a] }); this.tracer?.emit("merge", { low, middle, high, array: [...array] }); let i = lo; // next element of the left run (read from buf) let nextLeft = low; // next element of the left run (read from buf) let j = mid; // next element of the right run (read in place) let nextRight = middle; // next element of the right run (read in place) for (let k = lo; i < mid; k++) { for (let target = low; nextLeft < middle; target++) { const left = buf[i - lo]!; const left = leftCopy[nextLeft - low]!; const right = j < hi ? a[j]! : Infinity; // a used-up right run never wins const right = nextRight < high ? array[nextRight]! : Infinity; // a used-up right run never wins // ▸ which front bar is smaller, left copy or right run if (j < hi) this.tracer?.emit("compare", { lo, hi, i, j, left, right, array: [...a] }); if (nextRight < high) this.tracer?.emit("compare", { low, high, nextLeft, nextRight, left, right, array: [...array] }); const fromLeft = left <= right; // ties go left: the sort stays stable // ▸ write the smaller one into the next slot this.tracer?.emit("write", { lo, hi, from: fromLeft ? i : j, to: k, array: [...a] }); this.tracer?.emit("write", { low, high, from: fromLeft ? nextLeft : nextRight, to: target, array: [...array] }); a[k] = fromLeft ? left : right; array[target] = fromLeft ? left : right; if (fromLeft) i++; if (fromLeft) nextLeft++; else j++; else nextRight++; } }}