Randomized Shellsort

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);
	}
}