Library Sort

Insertion

Sorts by building a final sorted array one item at a time, inserting it into place.

Probabilistic

Uses random choices to reduce the probability of worst-case performance.

Out-of-Place

Requires auxiliary memory proportional to the input size (O(n)).

Unstable

Does not guarantee the relative order of elements with equal values.

Inserts randomized input into a sorted sparse array and periodically rebalances gaps.

Visualize Fullscreen

Demo

20 elements • 4x Speed

No Data

Did you know?

The name comes from leaving empty spaces on a bookshelf so a newly acquired book can be inserted without shifting every later book.
The original paper is titled Insertion Sort is O(n log n); that high-probability bound applies to its canonical method, while this visual version uses simpler quadratic-time scans.
A rebalance spreads the occupied keys across more physical slots without changing their logical order. This version also shuffles input before inserting, but its simple position scans do not inherit the original paper’s speed bound.

How it Works

Shuffle input values.
Binary-search the occupied keys for insertion rank.
Insert in a nearby gap; rebalance sparse slots at doubling rounds.

Complexity Analysis

Best Case

O(n \log n)

Average

O(n^2)

Worst Case

O(n^2)

Space

O(n)

Advantages

Gaps reduce local moves when space is available.
Shows the idea behind gapped insertion.

Disadvantages

This visualization scans and shifts occupied positions, so its runtime is quadratic.
Random shuffling removes stability.

Implementation

TypeScript simple-variants.ts

import type { NumericTrace } from './trace';

/** Random gap order, with a final gap-one pass guaranteeing full sorting. */
export function randomizedShellSort(trace: NumericTrace) {
	const n = trace.array.length;
	const gaps: number[] = [];
	for (let gap = Math.floor(n / 2); gap > 1; gap = Math.floor(gap / 2)) {
		gaps.push(gap);
	}
	for (let index = gaps.length - 1; index > 0; index--) {
		const random = Math.floor(Math.random() * (index + 1));
		[gaps[index], gaps[random]] = [gaps[random], gaps[index]];
	}
	gaps.push(1);
	for (const gap of gaps) {
		trace.note(`Randomized Shellsort: gapped insertion pass with gap ${gap}`);
		for (let index = gap; index < n; index++) {
			const value = trace.array[index];
			let position = index;
			while (
				position >= gap &&
				trace.compareValues(position - gap, index, trace.array[position - gap], value) > 0
			) {
				trace.write(position, trace.array[position - gap]);
				position -= gap;
			}
			if (position !== index) trace.write(position, value);
		}
	}
}

/** Gapped insertion with a randomized input order and periodic rebalancing. */
export function librarySort(trace: NumericTrace) {
	const n = trace.array.length;
	if (n < 2) return;
	const input = [...trace.array];
	for (let index = n - 1; index > 0; index--) {
		const random = Math.floor(Math.random() * (index + 1));
		[input[index], input[random]] = [input[random], input[index]];
	}
	const slots: Array<number | undefined> = new Array(n * 2 + 1).fill(undefined);
	let occupied: number[] = [];
	function rebalance() {
		const values = occupied.map((position) => slots[position] as number);
		slots.fill(undefined);
		occupied = [];
		for (let index = 0; index < values.length; index++) {
			const position = Math.floor(((index + 1) * slots.length) / (values.length + 1));
			slots[position] = values[index];
			occupied.push(position);
		}
		trace.note(`Rebalance ${values.length} values across gapped library slots`);
	}
	for (let inserted = 0; inserted < n; inserted++) {
		const value = input[inserted];
		let low = 0;
		let high = occupied.length;
		while (low < high) {
			const middle = low + Math.floor((high - low) / 2);
			trace.note(`Compare ${value} with library item ${slots[occupied[middle]]}`);
			if ((slots[occupied[middle]] as number) <= value) low = middle + 1;
			else high = middle;
		}
		const rank = low;
		const left = rank === 0 ? -1 : occupied[rank - 1];
		const right = rank === occupied.length ? slots.length : occupied[rank];
		if (right - left <= 1) rebalance();
		const newLeft = rank === 0 ? -1 : occupied[rank - 1];
		const newRight = rank === occupied.length ? slots.length : occupied[rank];
		let position = Math.floor((newLeft + newRight) / 2);
		if (position <= newLeft || position >= newRight || slots[position] !== undefined) {
			// A dense local run can occur before the next scheduled rebalance.
			// Shift its right side into the nearest gap, then open one slot.
			position = newRight;
			let gap = position;
			while (gap < slots.length && slots[gap] !== undefined) gap++;
			if (gap === slots.length) {
				rebalance();
				const afterLeft = rank === 0 ? -1 : occupied[rank - 1];
				const afterRight = rank === occupied.length ? slots.length : occupied[rank];
				position = Math.floor((afterLeft + afterRight) / 2);
			} else {
				for (let index = gap; index > position; index--) slots[index] = slots[index - 1];
				for (let index = rank; index < occupied.length; index++) occupied[index]++;
			}
		}
		slots[position] = value;
		occupied.splice(rank, 0, position);
		trace.note(`Insert ${value} into library gap ${position}`);
		if (((inserted + 1) & inserted) === 0 && inserted + 1 < n) rebalance();
	}
	for (let output = 0; output < n; output++) {
		trace.write(output, slots[occupied[output]] as number);
	}
}