algossorting

merge sort

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

updated october 2026

.md

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: yesties take from the left
in place: noneeds 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.¹ watch it happen, with the array from the classic merge sort diagram:²

start with eight numbers in no particular order.

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.

input

12 unsorted values

comparisons: 0
writes: 0
step: 1 of 112

pseudocode

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

try it

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

left

right

merged

0 of 0 right

both halves are sorted. which head goes into the merged list next?

tip: the left and right arrow keys work too

pseudocode

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

array size

3 levels of merging, 8 items each: 3 × 8 = 24 moves.

log₂ 8 = 3. double the array and you add one level, not double the levels. that's the log 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

"""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

/* 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

// 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

//! 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

/// 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

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³
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,⁴ java’s object sort,⁵ v8’s Array.prototype.sort⁶) merges natural runs and uses insertion sort on small pieces. rust’s stable sort is driftsort, another merge-based hybrid.⁷ go’s sort.Stable uses insertion sort on blocks of 20 plus an in-place merge⁸

practice

sort list (opens in a new tab): merge sort on a linked list
merge sorted array (opens in a new tab): just the merge step, done in place from the back
merge k sorted lists (opens in a new tab): 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

sources

merge sort (opens in a new tab) on wikipedia, which cites knuth, the art of computer programming, vol. 3, section 5.2.4. ↩
38, 27, 43, 3, 9, 82, 10 is the array in the merge sort algorithm diagram (opens in a new tab) on wikimedia commons. 19 is added here to make eight. ↩
joshua bloch, nearly all binary searches and mergesorts are broken (opens in a new tab), google research, 2006. ↩
tim peters’ design notes, listsort.txt (opens in a new tab), in cpython. newer versions use the powersort merge policy. ↩
Arrays.sort (opens in a new tab) in the java docs, which credit tim peters’ python sort for the object version. ↩
getting things sorted in v8 (opens in a new tab), the v8 blog, 2018. ↩
slice::sort (opens in a new tab) in the rust docs. ↩
sort.Stable (opens in a new tab) and its source (opens in a new tab). ↩

the idea

watch it run

try it

pseudocode

the merge, up close

why it’s n log n

implementations

pitfalls

variants

practice

sources

related

quicksortsoon

heap sortsoon

bfssoon