# merge sort

> split the array in half, sort each half, then merge the two sorted halves back together.

source: https://learning.anthnydas.com/algos/merge-sort/

## tl;dr

split in half, sort each half, then merge the two sorted halves.

- **time:** O(n log n) (best and worst case)
- **space:** O(n) (the merge buffer)
- **stable:** yes (ties take from the left)
- **in place:** no (needs the buffer)
- **reach for it:** guaranteed n log n, stable sorting, linked lists, data bigger than memory

## the idea

merge sort never compares two items that aren't both at the front of a sorted list. it gets those sorted lists by splitting the problem until the pieces are trivially sorted, then building back up. john von neumann described it in 1945.[^history] watch it happen, with the array from the classic merge sort diagram:[^diagram]

> **interactive figure:** an animation: eight numbers (38, 27, 43, 3, 9, 82, 10, 19) split in half three times down to single items, then merge back up one item at a time, smallest first: pairs, then fours, then the sorted array 3, 9, 10, 19, 27, 38, 43, 82.

start with eight numbers in no particular order.

split the array in half. each half is a smaller copy of the same problem.

keep splitting until every piece holds one number. one number is already sorted, so the recursion stops here.

now merge neighbors back together, always taking the smaller of the two front items. the pairs come out sorted.

merge the pairs into sorted fours. each merge walks its two inputs exactly once.

one last merge gives the sorted array. three levels of merging, eight items per level: that's where n log n comes from.

## watch it run

step through a real run. the top row is the array, the bottom row is the merge buffer. cyan is the left half, amber is the right half, and white is the item moving right now. the pseudocode on the right follows along.

> **interactive figure:** an interactive stepper: bars for a random array, split into halves and merged back through an aux buffer, with the matching pseudocode line highlighted and counters for comparisons and writes.

## try it

the whole algorithm hangs on one decision: which front item goes next. make the call.

> **interactive figure:** a practice exercise: given two sorted halves, pick whether the left or the right front item goes into the merged list next. on a tie, the left one goes first.

## pseudocode

```text
merge_sort(a, lo, hi):  # sorts a[lo:hi]
  if hi - lo <= 1: return  # 0 or 1 items: sorted
  mid = lo + (hi - lo) // 2
  merge_sort(a, lo, mid)
  merge_sort(a, mid, hi)
  merge(a, lo, mid, hi)

merge(a, lo, mid, hi):
  i, j = lo, mid
  for k in range(lo, hi):
    if j == hi or (i < mid and a[i] <= a[j]):
      aux[k] = a[i]; i += 1  # take left
    else:
      aux[k] = a[j]; j += 1  # take right
  a[lo:hi] = aux[lo:hi]  # copy back
```

ranges are half-open: `a[lo:hi]` covers `lo` up to but not including `hi`. that makes the base case `hi - lo <= 1` and the split point `mid` clean, with no plus or minus ones.

## the merge, up close

- two pointers: `i` at the front of the left half, `j` at the front of the right half
- each step compares `a[i]` with `a[j]`, copies the smaller one into `aux[k]`, and moves that pointer forward
- when one half runs out, the rest of the other half comes over as is
- ties: `a[i] <= a[j]` takes from the left. make it `<` and equal items can swap places, which breaks stability
- a merge of `hi - lo` items costs `hi - lo` steps. every item is written exactly once

## why it's n log n

> **interactive figure:** a recursion tree with a size picker. for n items there are log2 n levels of merging, and each level moves n items in total, so the work is n times log2 n.

- every level of the recursion halves each piece, so there are `log₂ n` levels of merging
- each level touches every item once while merging, so each level costs `n`
- `n` per level times `log₂ n` levels is O(n log n). as a recurrence: `T(n) = 2T(n/2) + n`
- space: the `aux` buffer holds `n` items, plus `log n` stack frames for the recursion

## implementations

each tab is the real file from the repo, checked by its tests (`python -m unittest`, `make test`, `go test`, `cargo test`, `swift test`, `vitest`).

`python/algos/merge_sort.py`

```python
"""top-down merge sort: stable, O(n log n) time in every case, O(n) extra space."""

from __future__ import annotations

from typing import Any, Callable, TypeVar

T = TypeVar("T")


def merge_sort(items: list[T], key: Callable[[T], Any] | None = None) -> list[T]:
    """Return a new sorted list. Equal items keep their original order."""
    a = list(items)
    aux = a[:]  # allocated once, reused by every merge
    k = key or (lambda x: x)

    def merge(lo: int, mid: int, hi: int) -> None:
        i, j = lo, mid
        for out in range(lo, hi):
            # <= takes from the left on ties, which keeps the sort stable
            if j >= hi or (i < mid and k(a[i]) <= k(a[j])):
                aux[out] = a[i]
                i += 1
            else:
                aux[out] = a[j]
                j += 1
        a[lo:hi] = aux[lo:hi]

    def sort(lo: int, hi: int) -> None:
        if hi - lo <= 1:
            return  # 0 or 1 items: already sorted
        mid = lo + (hi - lo) // 2
        sort(lo, mid)
        sort(mid, hi)
        merge(lo, mid, hi)

    sort(0, len(a))
    return a
```

`c/algos/merge_sort.c`

```c
/* top-down merge sort: stable, O(n log n) time in every case, O(n) extra space */
#include "merge_sort.h"

#include <stdlib.h>
#include <string.h>

/* combines the sorted halves a[lo..mid) and a[mid..hi) */
static void merge(int *a, int *aux, size_t lo, size_t mid, size_t hi) {
    size_t i = lo, j = mid;
    for (size_t k = lo; k < hi; k++) {
        /* <= takes from the left on ties, which keeps the sort stable */
        if (j >= hi || (i < mid && a[i] <= a[j])) aux[k] = a[i++];
        else aux[k] = a[j++];
    }
    memcpy(a + lo, aux + lo, (hi - lo) * sizeof *a);
}

static void sort_range(int *a, int *aux, size_t lo, size_t hi) {
    if (hi - lo <= 1) return; /* 0 or 1 items: already sorted */
    size_t mid = lo + (hi - lo) / 2;
    sort_range(a, aux, lo, mid);
    sort_range(a, aux, mid, hi);
    merge(a, aux, lo, mid, hi);
}

int merge_sort(int *a, size_t n) {
    if (n < 2) return 0;
    int *aux = malloc(n * sizeof *aux); /* allocated once, reused by every merge */
    if (!aux) return -1;
    sort_range(a, aux, 0, n);
    free(aux);
    return 0;
}
```

`go/algos/mergesort/mergesort.go`

```go
// Package mergesort is a reference top-down merge sort:
// stable, O(n log n) time in every case, O(n) extra space.
package mergesort

import "cmp"

// Sort sorts s in ascending order.
func Sort[S ~[]E, E cmp.Ordered](s S) {
	SortFunc(s, cmp.Compare[E])
}

// SortFunc sorts s with less-than-or-equal semantics from compare,
// keeping equal elements in their original order.
func SortFunc[S ~[]E, E any](s S, compare func(a, b E) int) {
	if len(s) < 2 {
		return
	}
	aux := make(S, len(s)) // allocated once, reused by every merge
	sortRange(s, aux, 0, len(s), compare)
}

func sortRange[S ~[]E, E any](s, aux S, lo, hi int, compare func(a, b E) int) {
	if hi-lo <= 1 {
		return // 0 or 1 items: already sorted
	}
	mid := lo + (hi-lo)/2
	sortRange(s, aux, lo, mid, compare)
	sortRange(s, aux, mid, hi, compare)
	merge(s, aux, lo, mid, hi, compare)
}

// merge combines the sorted halves s[lo:mid] and s[mid:hi].
func merge[S ~[]E, E any](s, aux S, lo, mid, hi int, compare func(a, b E) int) {
	i, j := lo, mid
	for k := lo; k < hi; k++ {
		// <= takes from the left on ties, which keeps the sort stable
		if j >= hi || (i < mid && compare(s[i], s[j]) <= 0) {
			aux[k] = s[i]
			i++
		} else {
			aux[k] = s[j]
			j++
		}
	}
	copy(s[lo:hi], aux[lo:hi])
}

// SortBottomUp is the iterative variant: merge runs of width 1, 2, 4, ...
// No recursion, same O(n log n) time and O(n) space.
func SortBottomUp[S ~[]E, E cmp.Ordered](s S) {
	n := len(s)
	if n < 2 {
		return
	}
	aux := make(S, n)
	for width := 1; width < n; width *= 2 {
		for lo := 0; lo < n-width; lo += 2 * width {
			merge(s, aux, lo, lo+width, min(lo+2*width, n), cmp.Compare[E])
		}
	}
}
```

`rust/algos/src/merge_sort.rs`

```rust
//! top-down merge sort: stable, O(n log n) time in every case, O(n) extra space

use std::cmp::Ordering;

/// Sorts `v` in ascending order, keeping equal elements in their original order.
pub fn merge_sort<T: Ord + Clone>(v: &mut [T]) {
    merge_sort_by(v, |a, b| a.cmp(b));
}

/// Sorts `v` with `cmp`, keeping equal elements in their original order.
pub fn merge_sort_by<T: Clone, F: FnMut(&T, &T) -> Ordering>(v: &mut [T], mut cmp: F) {
    if v.len() < 2 {
        return;
    }
    let mut aux = v.to_vec(); // allocated once, reused by every merge
    sort_range(v, &mut aux, 0, v.len(), &mut cmp);
}

fn sort_range<T: Clone, F: FnMut(&T, &T) -> Ordering>(
    v: &mut [T],
    aux: &mut [T],
    lo: usize,
    hi: usize,
    cmp: &mut F,
) {
    if hi - lo <= 1 {
        return; // 0 or 1 items: already sorted
    }
    let mid = lo + (hi - lo) / 2;
    sort_range(v, aux, lo, mid, cmp);
    sort_range(v, aux, mid, hi, cmp);
    merge(v, aux, lo, mid, hi, cmp);
}

/// Combines the sorted halves `v[lo..mid]` and `v[mid..hi]`.
fn merge<T: Clone, F: FnMut(&T, &T) -> Ordering>(
    v: &mut [T],
    aux: &mut [T],
    lo: usize,
    mid: usize,
    hi: usize,
    cmp: &mut F,
) {
    let (mut i, mut j) = (lo, mid);
    for slot in &mut aux[lo..hi] {
        // "not greater" takes from the left on ties, which keeps the sort stable
        if j >= hi || (i < mid && cmp(&v[i], &v[j]) != Ordering::Greater) {
            *slot = v[i].clone();
            i += 1;
        } else {
            *slot = v[j].clone();
            j += 1;
        }
    }
    v[lo..hi].clone_from_slice(&aux[lo..hi]);
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn sorts() {
        let cases: [(&[i32], &[i32]); 5] = [
            (&[38, 27, 43, 3, 9, 82, 10], &[3, 9, 10, 27, 38, 43, 82]),
            (&[], &[]),
            (&[5], &[5]),
            (&[3, 1, 3, 1], &[1, 1, 3, 3]),
            (&[4, 3, 2, 1], &[1, 2, 3, 4]),
        ];
        for (input, want) in cases {
            let mut got = input.to_vec();
            merge_sort(&mut got);
            assert_eq!(got, want, "input {input:?}");
        }
    }

    #[test]
    fn is_stable() {
        let mut v = vec![(2, 'a'), (1, 'b'), (2, 'c'), (1, 'd')];
        merge_sort_by(&mut v, |x, y| x.0.cmp(&y.0));
        let ids: Vec<char> = v.iter().map(|r| r.1).collect();
        assert_eq!(ids, ['b', 'd', 'a', 'c']);
    }
}
```

`swift/algos/MergeSort.swift`

```swift
/// Top-down merge sort: stable, O(n log n) time in every case, O(n) extra space.
/// Returns a new array; equal items keep their original order.
public func mergeSort<T>(_ items: [T], by areInIncreasingOrder: (T, T) -> Bool) -> [T] {
    var a = items
    var aux = items // allocated once, reused by every merge

    // combines the sorted halves a[lo..<mid] and a[mid..<hi]
    func merge(_ lo: Int, _ mid: Int, _ hi: Int) {
        var i = lo, j = mid
        for k in lo..<hi {
            // take from the right only when it's strictly smaller, so ties stay in order (stable)
            if j >= hi || (i < mid && !areInIncreasingOrder(a[j], a[i])) {
                aux[k] = a[i]
                i += 1
            } else {
                aux[k] = a[j]
                j += 1
            }
        }
        a[lo..<hi] = aux[lo..<hi]
    }

    func sort(_ lo: Int, _ hi: Int) {
        guard hi - lo > 1 else { return } // 0 or 1 items: already sorted
        let mid = lo + (hi - lo) / 2
        sort(lo, mid)
        sort(mid, hi)
        merge(lo, mid, hi)
    }

    sort(0, a.count)
    return a
}

/// Sorts in ascending order.
public func mergeSort<T: Comparable>(_ items: [T]) -> [T] {
    mergeSort(items, by: <)
}
```

`site/src/visuals/merge-sort/merge-sort.ts`

```ts
const ascending = <T>(a: T, b: T) => (a < b ? -1 : a > b ? 1 : 0);

/**
 * Stable top-down merge sort. Returns a new sorted array.
 * O(n log n) time in every case, O(n) extra space for the aux buffer.
 */
export function mergeSort<T>(items: readonly T[], compare: (a: T, b: T) => number = ascending): T[] {
  const a = [...items];
  const aux = new Array<T>(a.length); // allocated once, reused by every merge

  function sort(lo: number, hi: number): void {
    if (hi - lo <= 1) return; // 0 or 1 items: already sorted
    const mid = lo + Math.floor((hi - lo) / 2);
    sort(lo, mid);
    sort(mid, hi);
    merge(lo, mid, hi);
  }

  function merge(lo: number, mid: number, hi: number): void {
    let i = lo; // head of the left half  a[lo:mid]
    let j = mid; // head of the right half a[mid:hi]
    for (let k = lo; k < hi; k++) {
      // `<=` takes from the left on ties, which is what keeps the sort stable
      if (j >= hi || (i < mid && compare(a[i], a[j]) <= 0)) aux[k] = a[i++];
      else aux[k] = a[j++];
    }
    for (let k = lo; k < hi; k++) a[k] = aux[k];
  }

  sort(0, a.length);
  return a;
}
```

## pitfalls

- off-by-one ranges. use half-open `[lo, hi)` and stop when `hi - lo <= 1`
- `<` instead of `<=` in the merge quietly breaks stability
- allocating a new buffer inside every merge works but churns memory. allocate once, pass it down
- `mid = (lo + hi) / 2` can overflow with fixed-size integers. `lo + (hi - lo) / 2` can't[^overflow]
- forgetting to copy the leftovers when one half runs out

## variants

- **bottom-up.** no recursion: merge runs of width 1, 2, 4, and so on until one run covers the array. same O(n log n). `SortBottomUp` in the go file
- **linked lists.** merging relinks nodes instead of copying them, so there's no buffer and no random access needed. it's the usual way to sort a linked list
- **k-way merge.** merge k sorted lists with a min-heap in O(n log k). it's the core of external sorting, when the data doesn't fit in memory
- **natural merge sort.** find the runs that are already sorted and merge those. fast on nearly sorted input
- **hybrids in the wild.** timsort (python,[^cpython] java's object sort,[^java] v8's `Array.prototype.sort`[^v8]) merges natural runs and uses insertion sort on small pieces. rust's stable `sort` is driftsort, another merge-based hybrid.[^rust] go's `sort.Stable` uses insertion sort on blocks of 20 plus an in-place merge[^go]

merge sort is the stable, predictable choice. quicksort is usually faster in memory because it works in place and is cache friendly, but its worst case is O(n²) and it isn't stable.

## practice

- [sort list](https://leetcode.com/problems/sort-list/): merge sort on a linked list
- [merge sorted array](https://leetcode.com/problems/merge-sorted-array/): just the merge step, done in place from the back
- [merge k sorted lists](https://leetcode.com/problems/merge-k-sorted-lists/): the k-way merge with a heap
- count inversions: merge sort with a counter. every time the right side wins, add the number of items left in the left half

[^history]: [merge sort](https://en.wikipedia.org/wiki/Merge_sort) on wikipedia, which cites knuth, _the art of computer programming_, vol. 3, section 5.2.4.

[^diagram]: 38, 27, 43, 3, 9, 82, 10 is the array in the [merge sort algorithm diagram](https://commons.wikimedia.org/wiki/File:Merge_sort_algorithm_diagram.svg) on wikimedia commons. 19 is added here to make eight.

[^overflow]: joshua bloch, [nearly all binary searches and mergesorts are broken](https://research.google/blog/extra-extra-read-all-about-it-nearly-all-binary-searches-and-mergesorts-are-broken/), google research, 2006.

[^cpython]: tim peters' design notes, [listsort.txt](https://github.com/python/cpython/blob/main/Objects/listsort.txt), in cpython. newer versions use the powersort merge policy.

[^java]: [Arrays.sort](https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/Arrays.html) in the java docs, which credit tim peters' python sort for the object version.

[^v8]: [getting things sorted in v8](https://v8.dev/blog/array-sort), the v8 blog, 2018.

[^rust]: [slice::sort](https://doc.rust-lang.org/std/primitive.slice.html#method.sort) in the rust docs.

[^go]: [sort.Stable](https://pkg.go.dev/sort#Stable) and its [source](https://github.com/golang/go/blob/master/src/sort/zsortinterface.go).

## related

- https://learning.anthnydas.com/algos/quicksort.md
- https://learning.anthnydas.com/algos/heap-sort.md
- https://learning.anthnydas.com/algos/bfs.md