Distributed Bucket Sort

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

function range(trace: NumericTrace) {
	let minimum = Infinity;
	let maximum = -Infinity;
	for (let index = 0; index < trace.array.length; index++) {
		const value = trace.array[index];
		if (value < minimum) minimum = value;
		if (value > maximum) maximum = value;
		trace.note(`Inspect ${value} for distribution range`, { [index]: 'bg-vis-compare' });
	}
	return { minimum, maximum };
}

function insertionSort(values: number[], trace: NumericTrace, label: string) {
	for (let index = 1; index < values.length; index++) {
		const value = values[index];
		let position = index;
		while (position > 0) {
			trace.note(`${label}: compare ${values[position - 1]} with ${value}`);
			if (values[position - 1] <= value) break;
			values[position] = values[position - 1];
			position--;
		}
		values[position] = value;
	}
}

export function bucketSort(trace: NumericTrace) {
	const n = trace.array.length;
	if (n < 2) return;
	const { minimum, maximum } = range(trace);
	if (minimum === maximum) return;
	const count = n;
	const buckets = Array.from({ length: count }, () => [] as number[]);
	for (let index = 0; index < n; index++) {
		const value = trace.array[index];
		const bucket = Math.min(
			count - 1,
			Math.floor(((value - minimum) * count) / (maximum - minimum + 1))
		);
		buckets[bucket].push(value);
		trace.note(`Place ${value} in bucket ${bucket}`, { [index]: 'bg-vis-write' });
	}
	let output = 0;
	for (let bucket = 0; bucket < count; bucket++) {
		insertionSort(buckets[bucket], trace, `Bucket ${bucket}`);
		for (const value of buckets[bucket]) trace.write(output++, value);
	}
}

/** Map, shuffle by range, local sort, then concatenate virtual workers' output. */
export function distributedBucketSort(trace: NumericTrace) {
	const n = trace.array.length;
	if (n < 2) return;
	const { minimum, maximum } = range(trace);
	if (minimum === maximum) return;
	const workers = Math.min(4, n);
	const buckets = Array.from({ length: workers }, () => [] as number[]);
	const shardSize = Math.ceil(n / workers);
	for (let index = 0; index < n; index++) {
		const value = trace.array[index];
		const mapper = Math.floor(index / shardSize);
		const target = Math.min(
			workers - 1,
			Math.floor(((value - minimum) * workers) / (maximum - minimum + 1))
		);
		buckets[target].push(value);
		trace.note(`Mapper ${mapper} sends ${value} to worker ${target}`, {
			[index]: 'bg-vis-write'
		});
	}
	let output = 0;
	for (let worker = 0; worker < workers; worker++) {
		trace.note(`Worker ${worker} sorts its received bucket`);
		const values = buckets[worker];
		function sort(start: number, end: number) {
			if (end - start < 2) return;
			const middle = start + Math.floor((end - start) / 2);
			sort(start, middle);
			sort(middle, end);
			const source = values.slice(start, end);
			let left = 0;
			let right = middle - start;
			for (let position = start; position < end; position++) {
				if (left < middle - start && (right >= end - start || source[left] <= source[right])) {
					if (right < end - start)
						trace.note(`Worker ${worker} compares ${source[left]} and ${source[right]}`);
					values[position] = source[left++];
				} else {
					if (left < middle - start)
						trace.note(`Worker ${worker} compares ${source[left]} and ${source[right]}`);
					values[position] = source[right++];
				}
			}
		}
		sort(0, values.length);
		for (const value of buckets[worker]) trace.write(output++, value);
	}
}

export function pigeonholeSort(trace: NumericTrace) {
	const n = trace.array.length;
	if (n < 2) return;
	const { minimum, maximum } = range(trace);
	if (!Number.isSafeInteger(minimum) || !Number.isSafeInteger(maximum)) {
		throw new Error('Pigeonhole sort requires safe integers');
	}
	const span = maximum - minimum + 1;
	if (span > 1_000_000) throw new Error('Pigeonhole key range exceeds one million slots');
	const holes = new Array<number>(span).fill(0);
	for (let index = 0; index < n; index++) {
		const value = trace.array[index];
		holes[value - minimum]++;
		trace.note(`Place ${value} in pigeonhole ${value - minimum}`, {
			[index]: 'bg-vis-write'
		});
	}
	let output = 0;
	for (let hole = 0; hole < span; hole++) {
		for (let count = holes[hole]; count > 0; count--) {
			trace.write(output++, hole + minimum);
		}
	}
}

/** Neubert's classification, in-place permutation, and insertion cleanup. */
export function flashSort(trace: NumericTrace) {
	const n = trace.array.length;
	if (n < 2) return;
	const { minimum, maximum } = range(trace);
	if (minimum === maximum) return;
	const classes = Math.max(2, Math.floor(0.43 * n));
	const classOf = (value: number) =>
		Math.min(classes - 1, Math.floor(((classes - 1) * (value - minimum)) / (maximum - minimum)));
	const ends = new Array<number>(classes).fill(0);
	ends[0] = -1;
	for (const value of trace.array) ends[classOf(value)]++;
	for (let index = 1; index < classes; index++) ends[index] += ends[index - 1];
	let maxIndex = 0;
	for (let position = 1; position < n; position++) {
		if (trace.array[position] > trace.array[maxIndex]) maxIndex = position;
	}
	trace.swap(0, maxIndex);
	let moved = 0;
	let index = 0;
	let currentClass = classes - 1;
	while (moved < n) {
		while (index > ends[currentClass]) {
			index++;
			if (index >= n) throw new Error('Flashsort permutation invariant failed');
			currentClass = classOf(trace.array[index]);
		}
		let flash = trace.array[index];
		while (index <= ends[currentClass]) {
			currentClass = classOf(flash);
			const destination = ends[currentClass];
			const displaced = trace.array[destination];
			trace.write(destination, flash, `Flash ${flash} into class ${currentClass}`);
			ends[currentClass]--;
			flash = displaced;
			moved++;
		}
	}
	for (let right = 1; right < n; right++) {
		const value = trace.array[right];
		let left = right;
		while (left > 0 && trace.compareValues(left - 1, right, trace.array[left - 1], value) > 0) {
			trace.write(left, trace.array[left - 1]);
			left--;
		}
		if (left !== right) trace.write(left, value);
	}
}

/** Integer spreadsort: MSD radix partitions with comparison-sort leaves. */
export function spreadSort(trace: NumericTrace) {
	if (
		!trace.array.every(
			(value) => Number.isInteger(value) && value >= -2147483648 && value <= 2147483647
		)
	) {
		throw new Error('Integer spreadsort requires signed 32-bit integers');
	}
	function key(value: number) {
		return (value ^ -2147483648) >>> 0;
	}
	function insertion(start: number, end: number) {
		for (let index = start + 1; index < end; index++) {
			const value = trace.array[index];
			let position = index;
			while (
				position > start &&
				trace.compareValues(position - 1, index, trace.array[position - 1], value) > 0
			) {
				trace.write(position, trace.array[position - 1]);
				position--;
			}
			if (position !== index) trace.write(position, value);
		}
	}
	function sort(start: number, end: number, bit: number) {
		if (end - start < 2) return;
		if (end - start <= 16 || bit < 0) {
			insertion(start, end);
			return;
		}
		let left = start;
		let right = end - 1;
		while (left <= right) {
			while (left <= right && ((key(trace.array[left]) >>> bit) & 1) === 0) left++;
			while (left <= right && ((key(trace.array[right]) >>> bit) & 1) === 1) right--;
			if (left < right) trace.swap(left++, right--);
		}
		trace.note(`Split values by bit ${bit} at index ${left}`);
		sort(start, left, bit - 1);
		sort(left, end, bit - 1);
	}
	sort(0, trace.array.length, 31);
}