Home/Sorting/Merge sort
Search algorithmsCTRL K

Merge sort

· divide and conquer · stable
/sorting/merge-sort
COMPARISONS
0
≈ n log₂ n − n expected
WRITES
0
from the buffer back into a
DEPTH
0/ 6
recursion now / max
RANGE
[0, 23]
current call
MERGES
0
completed so far
split pointcomparingwritten backdone
n = 24 · seed 7 · 296 steps
step 0 / 295
Size24
merge_sort.ts
1
function mergeSort(array: number[], low: number, high: number) {
2
  if (high - low < 1) return;
3
  const middle = (low + high) >> 1;
4
  mergeSort(array, low, middle);
5
  mergeSort(array, middle + 1, high);
6
  const merged: number[] = [];
7
  let i = low, j = middle + 1;
8
  while (i <= middle && j <= high) {
9
    if (array[i] <= array[j]) merged.push(array[i++]);
10
    else merged.push(array[j++]);
11
  }
12
  while (i <= middle) merged.push(array[i++]);
13
  while (j <= high) merged.push(array[j++]);
14
  for (let k = 0; k < merged.length; k++) array[low + k] = merged[k];
15
}
CURRENT STEP
line 1

Start: 24 values. mergeSort(a, 0, 23) splits until the ranges have one element, then merges.

// how it works

Understanding Merge sort

merge sort · the sort that never has a bad day
01

The idea

Merge sort splits the range in half, sorts each half recursively, and merges the two sorted halves by repeatedly taking the smaller front element. Ranges of one element are sorted by definition, so the recursion bottoms out immediately and all the work happens in the merges.

Every level of the recursion merges n elements in total, and there are log₂ n levels, so the cost is n log n whatever the input. The price is the buffer: merging in place is possible but awkward, so the textbook version copies into a temporary array and back.

02

The four stages

1
splitmiddle ← (low + high) / 2
2
comparefront of the left half vs the right
3
mergesmaller one goes to the buffer
4
copy backbuffer overwrites [low, high]
03

Complexity

best
O(n log n)even sorted input is split and merged
average
O(n log n)≈ n log₂ n − n comparisons
worst
O(n log n)no bad input exists
space
O(n)the merge buffer
04

Versus its siblings

COMPARISONS AT N = 1 000
bubble
499,500
insertion
250,000
heap
17,000
quick
13,900
merge
8,700
random input · quick sort is faster in practice through cache and fewer moves
05

Pseudocode

MERGESORT(array, low, high)
  if high − low < 1: return
  middle ← ⌊(low + high) / 2⌋
  MERGESORT(array, low, middle); MERGESORT(array, middle + 1, high)
  merge the sorted halves into merged, smaller front first
  copy merged back into array[low..high]
06

When to use

Whenever stability matters: sorting records by one field without scrambling the order of equal ones. It is the sort behind Java's object sort and Python's sorted.
Linked lists and external sorting: merging needs only sequential access, so it works on tapes, files and lists.
07

Pitfalls

The O(n) buffer: on huge arrays or tight memory, quick sort or heap sort sort in place.
Allocating the buffer inside every merge is the classic performance bug; allocate once.
The naive version keeps merging already sorted runs; Tim sort detects them and skips the work.
08

History

John von Neumann wrote merge sort in 1945 as one of the first programs for the EDVAC, and described it formally with Herman Goldstine in 1948. It is the ancestor of Tim sort, which Tim Peters built for Python in 2002 and which Java and Android adopted later.

Back to Sorting