Sorting.

01 / The idea

You sort all day. You rarely write the sort.

A library’s returns desk ends each hour with a cart of books. The scanner lists them by title. The shelver walks a fixed route, shelf 1 to shelf 4, and wants the cart in that order, with each shelf’s books already alphabetical so they slide straight into place.

You do the same thing in code. toSorted on a list of rows. slices.SortStableFunc on a slice of structs. A data grid that sorts by owner when you click its header, and somehow keeps each owner’s tasks in the order you sorted them a moment ago. That last part is not luck. JavaScript’s sort has been required to be stable since ES2019, and you have been relying on it every time a multi-column sort worked.

Sorting puts items in order using one question: how do these two compare? This lesson builds a sort with the same shape as the stable sorts in V8 and Go: sort small piles by inserting one item at a time, then merge neighboring piles until one is left.

02 / Name the rule

Every neighbor in order, and every tie where it started.

A list is sorted when no item compares greater than the one after it. The comparator decides what that means. It returns a negative number when the first item comes first, a positive number when the second does, and zero for a tie. It must give the same answer for the same pair every time and agree with itself across pairs. Otherwise the result is not defined: ECMAScript calls the order implementation-defined, and Go requires a strict weak ordering.

A sort is stable when items that tie keep their original order. Sort the scanner’s alphabetical list by shelf with a stable sort, and every shelf stays alphabetical, because books on the same shelf tie and never pass each other. An unstable sort still puts the shelves in order, and may scramble the titles within them.

This sort has two phases. Insertion walks each pile of four and slides every book back past the books that belong after it, stopping at the first one that does not. Merging takes two sorted piles and keeps moving whichever front book comes first, taking from the left pile on a tie. After each merging pass the piles are twice as long.

The invariant: after insertion, every pile is sorted and stable, and after each merge pass, every pile of the new length is sorted and stable. Each pass doubles the pile length, so the passes stop once one pile covers the whole cart.

03 / Follow one operation

Eight books, two piles, and three ties in the merge.

The cart holds eight books in title order: Beloved, Dune, Emma, Frankenstein, Hamlet, Ivanhoe, Jane Eyre, and Middlemarch. Their shelves are 2, 3, 1, 2, 4, 1, 2, and 1. Sort by shelf, with piles of four.

Before you watch, predict the final order, and which book comes first on shelf 2. The animation replays each recorded comparison, swap, and move. Try it lets you shuffle the cart, change the pile size, and sort by title or by shelf.

04 / Read the shape

The sort puts things in order. The library decides what order means.

Basic form is sortStable alone: insertion-sorted blocks of four, bottom-up merges, and a trace of every comparison, for any items and any comparator. In the wild is shelvingOrder, which owns the library’s rules. A title must be printable ASCII and 1 to 120 characters, and a shelf a whole number from 1 to 99. Titles file without a leading “A”, “An”, or “The”, ignoring case and extra spaces. The order is shelf first, then filing title, with anything still tied left in the order it was returned.

Notice that shelvingOrder works out each filing title once, before sorting. The comparator runs about n log n times, so building the same lowercase string inside it would repeat that work on every comparison.

export type Step = {
	kind: 'block' | 'compare' | 'swap' | 'merge' | 'take' | 'pass';
	/** block and merge: start; compare and swap: left index; take: source index; pass: run width before. */
	a: number;
	/** block: end; merge: middle; compare and swap: right index; take: destination index; pass: run width after. */
	b: number;
	/** compare: the comparator's sign; merge: end; take: 0 from the left run, 1 from the right; otherwise -1. */
	c: number;
};
export type Sorted<T> = { items: T[]; comparisons: number; steps: Step[] };
export type SortOptions = { blockSize?: number; trace?: boolean };

// Sort small blocks by insertion, then merge neighboring runs until one run is left.
// Stable: items the comparator calls equal keep their input order. The input is not changed.
export function sortStable<T>(
	input: readonly T[],
	compare: (a: T, b: T) => number,
	{ blockSize = 4, trace = false }: SortOptions = {}
): Sorted<T> {
	if (!Number.isInteger(blockSize) || blockSize < 1)
		throw new RangeError('Block size must be a whole number of at least 1.');
	const n = input.length;
	let items = [...input];
	const steps: Step[] = [];
	let comparisons = 0;
	const record = (kind: Step['kind'], a: number, b: number, c = -1) => {
		if (trace) steps.push({ kind, a, b, c });
	};
	const order = (x: T, y: T) => {
		comparisons++;
		const result = compare(x, y);
		return result > 0 ? 1 : result < 0 ? -1 : 0; // NaN counts as a tie
	};

	for (let lo = 0; lo < n; lo += blockSize) {
		const hi = Math.min(lo + blockSize, n);
		record('block', lo, hi);
		for (let i = lo + 1; i < hi; i++) {
			for (let j = i; j > lo; j--) {
				const sign = order(items[j - 1], items[j]);
				record('compare', j - 1, j, sign);
				if (sign <= 0) break; // equal items never pass each other
				[items[j - 1], items[j]] = [items[j], items[j - 1]];
				record('swap', j - 1, j);
			}
		}
	}

	for (let width = blockSize; width < n; width *= 2) {
		const merged: T[] = new Array(n);
		for (let lo = 0; lo < n; lo += 2 * width) {
			const mid = Math.min(lo + width, n);
			const hi = Math.min(lo + 2 * width, n);
			if (mid < hi) record('merge', lo, mid, hi);
			let i = lo;
			let j = mid;
			let k = lo;
			while (i < mid && j < hi) {
				const sign = order(items[i], items[j]);
				record('compare', i, j, sign);
				if (sign <= 0) {
					merged[k] = items[i]; // a tie takes from the left run
					record('take', i, k, 0);
					i++;
				} else {
					merged[k] = items[j];
					record('take', j, k, 1);
					j++;
				}
				k++;
			}
			for (; i < mid; i++, k++) {
				merged[k] = items[i];
				record('take', i, k, 0);
			}
			for (; j < hi; j++, k++) {
				merged[k] = items[j];
				record('take', j, k, 1);
			}
		}
		items = merged;
		record('pass', width, width * 2);
	}
	return { items, comparisons, steps };
}

type Step struct {
	Kind string `json:"kind"`
	// block and merge: start; compare and swap: left index; take: source index; pass: run width before.
	A int `json:"a"`
	// block: end; merge: middle; compare and swap: right index; take: destination index; pass: run width after.
	B int `json:"b"`
	// compare: the comparator's sign; merge: end; take: 0 from the left run, 1 from the right; otherwise -1.
	C int `json:"c"`
}

type Sorted[T any] struct {
	Items       []T
	Comparisons int
	Steps       []Step
}

// SortOptions leaves BlockSize 0 to mean the default of 4.
type SortOptions struct {
	BlockSize int
	Trace     bool
}

// SortStable sorts small blocks by insertion, then merges neighboring runs until one
// run is left. It is stable: items cmp calls equal keep their input order. The input
// slice is not changed.
func SortStable[T any](input []T, cmp func(a, b T) int, options SortOptions) Sorted[T] {
	blockSize := options.BlockSize
	if blockSize == 0 {
		blockSize = 4
	}
	if blockSize < 1 {
		panic("block size must be at least 1")
	}
	n := len(input)
	items := append([]T(nil), input...)
	result := Sorted[T]{}
	record := func(kind string, a, b, c int) {
		if options.Trace {
			result.Steps = append(result.Steps, Step{kind, a, b, c})
		}
	}
	order := func(x, y T) int {
		result.Comparisons++
		switch r := cmp(x, y); {
		case r > 0:
			return 1
		case r < 0:
			return -1
		}
		return 0
	}

	for lo := 0; lo < n; lo += blockSize {
		hi := min(lo+blockSize, n)
		record("block", lo, hi, -1)
		for i := lo + 1; i < hi; i++ {
			for j := i; j > lo; j-- {
				sign := order(items[j-1], items[j])
				record("compare", j-1, j, sign)
				if sign <= 0 {
					break // equal items never pass each other
				}
				items[j-1], items[j] = items[j], items[j-1]
				record("swap", j-1, j, -1)
			}
		}
	}

	for width := blockSize; width < n; width *= 2 {
		merged := make([]T, n)
		for lo := 0; lo < n; lo += 2 * width {
			mid, hi := min(lo+width, n), min(lo+2*width, n)
			if mid < hi {
				record("merge", lo, mid, hi)
			}
			i, j, k := lo, mid, lo
			for i < mid && j < hi {
				sign := order(items[i], items[j])
				record("compare", i, j, sign)
				if sign <= 0 {
					merged[k] = items[i] // a tie takes from the left run
					record("take", i, k, 0)
					i++
				} else {
					merged[k] = items[j]
					record("take", j, k, 1)
					j++
				}
				k++
			}
			for ; i < mid; i, k = i+1, k+1 {
				merged[k] = items[i]
				record("take", i, k, 0)
			}
			for ; j < hi; j, k = j+1, k+1 {
				merged[k] = items[j]
				record("take", j, k, 1)
			}
		}
		items = merged
		record("pass", width, width*2, -1)
	}
	result.Items = items
	return result
}

05 / Try a decision

Which book goes first?

Merging is where stability is kept or lost, one comparison at a time. Decide before the feedback does.

06 / Follow the cost

No comparison sort can average much below n log₂ n.

Here is every operation at a glance, for n books. The rest of this section is about the first row, and why nothing that only compares can beat it by much.

Watch the merge again. Every comparison moved one book into the merged order, so merging two piles of four took at most seven comparisons. Each pass does that across the whole cart, and each pass doubles the pile length, so a cart of n books needs about log₂(n/4) passes. That is where n log n comes from.

Why can’t a cleverer sort do much better? A sort that only compares has to tell apart all n! possible orders of its input, and each comparison has two outcomes, so on average it needs at least log₂(n!) comparisons. For eight books that is about 15.3, so none can promise fewer than 16, and this sort averaged 16.3 over 400 shuffled carts. For 1,024 books, none can promise fewer than 8,770. This sort averaged 9,011, and insertion sort alone averaged 262,831.

Order already in the input helps one phase. Insertion sort needs one comparison per book on a cart that is already sorted. The merges here still compare their front books, so a sorted cart of 1,024 books costs 4,864 comparisons. TimSort looks for runs that are already in order and merges those, which is how the built-in sort finishes sorted input so quickly.

These are comparisons, not milliseconds. Copying into the second array, the trace, and drawing are extra, and comparing two long titles costs more than comparing two shelf numbers.

07 / Give it a real job

One sort per cart, with the rules written down.

At the returns desk, the scanner sends the cart’s books to shelvingOrder, and the shelver’s screen lists them in the order it returns. Everything that makes the order right for this library lives in the comparator and the checks before it. The sort itself never changes.

What it leaves out is a decision too. Titles are compared as ASCII, so a catalog with accented titles needs Intl.Collator or Go’s collate package, and both languages must use the same collation or they will disagree. The shelving route is fixed as shelf numbers, so renumbering the shelves changes every order. And a whole library’s catalog does not get sorted in memory: a database index keeps it in order as books are added, and ORDER BY reads it back.

import { useState } from 'react';

// due is an ISO date, so comparing it as text compares dates.
type Task = { title: string; owner: string; due: string };
type Column = keyof Task;

const tasks: Task[] = [
	{ title: 'Fix login redirect', owner: 'Sam', due: '2026-09-18' },
	{ title: 'Draft release notes', owner: 'Ari', due: '2026-09-16' },
	{ title: 'Review billing copy', owner: 'Sam', due: '2026-09-16' },
	{ title: 'Rotate API keys', owner: 'Ari', due: '2026-09-18' }
];
const columns: Column[] = ['title', 'owner', 'due'];

export function TaskTable() {
	const [rows, setRows] = useState(tasks);

	function sortBy(column: Column) {
		// toSorted returns a new array. rows.sort() would reorder the array React
		// already holds, and handing React that same array does not re-render.
		// The sort is stable, so rows that tie keep the order from the last click:
		// click "due", then "owner", and each owner's tasks stay in due-date order.
		setRows((current) => current.toSorted((a, b) => a[column].localeCompare(b[column])));
	}

	return (
		<table>
			<thead>
				<tr>
					{columns.map((column) => (
						<th key={column}>
							<button onClick={() => sortBy(column)}>{column}</button>
						</th>
					))}
				</tr>
			</thead>
			<tbody>
				{rows.map((row) => (
					<tr key={row.title}>
						<td>{row.title}</td>
						<td>{row.owner}</td>
						<td>{row.due}</td>
					</tr>
				))}
			</tbody>
		</table>
	);
}

08 / Make the call

Sort less, or sort smarter, before you sort more.

Use the built-in sort, and spend your effort on the comparator: toSorted or sort in TypeScript, slices.SortStableFunc in Go when ties matter, and slices.SortFunc when they do not.

Look elsewhere when the job changes. Lists that are already sorted: merge them. The top ten out of a million: keep a binary heap of ten instead of sorting everything. Keys that are small whole numbers, like shelves 1 to 99: counting sort files n books into 99 shelf buckets with one pass over the books and one over the shelves, without comparing books at all. Data that lives in a database: ORDER BY with an index. Repeated searches through the sorted result: binary search.

09 / Take the idea with you

Explain it without saying “merge sort.”

“I sort small piles by sliding each book back past the ones that belong after it. Then I merge the piles in pairs: I keep taking whichever front book comes first, and on a tie I take the left one. Each round the piles double, until one pile holds everything.” That describes the mechanism. The name is what you call it in a review.

Before moving on, explain three things without the name: why Beloved stayed ahead of Frankenstein, why merging two piles of four takes at most seven comparisons, and why no sort that only compares can promise fewer than 16 comparisons on eight books. Then find a sort in your own code and check whether anything depends on ties keeping their order.