In-Place Merge Sort

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

type Run = { start: number; end: number };

function merge(trace: NumericTrace, start: number, middle: number, end: number) {
	const source = trace.array.slice(start, end);
	let left = 0;
	let right = middle - start;
	const leftEnd = right;
	const rightEnd = end - start;
	trace.note(`Merge sorted runs [${start}, ${middle}) and [${middle}, ${end})`);
	for (let output = start; output < end; output++) {
		if (
			left < leftEnd &&
			(right >= rightEnd ||
				trace.compareValues(start + left, start + right, source[left], source[right]) <= 0)
		) {
			trace.write(output, source[left++]);
		} else {
			trace.write(output, source[right++]);
		}
	}
}

export function bottomUpMergeSort(trace: NumericTrace) {
	const n = trace.array.length;
	for (let width = 1; width < n; width *= 2) {
		trace.note(`Merge runs of width ${width}`);
		for (let start = 0; start < n; start += width * 2) {
			const middle = Math.min(start + width, n);
			const end = Math.min(start + width * 2, n);
			if (middle < end) merge(trace, start, middle, end);
		}
	}
}

/** Natural runs remain in input order, preserving equal-key stability. */
export function naturalMergeSort(trace: NumericTrace) {
	const n = trace.array.length;
	if (n < 2) return;
	for (;;) {
		const runs: Run[] = [];
		for (let start = 0; start < n; ) {
			let end = start + 1;
			if (end < n) {
				const descending = trace.compare(end - 1, end) > 0;
				while (end < n) {
					const comparison = trace.compare(end - 1, end);
					if (descending ? comparison <= 0 : comparison > 0) break;
					end++;
				}
				if (descending) {
					trace.note(`Reverse descending run [${start}, ${end})`);
					for (let left = start, right = end - 1; left < right; left++, right--) {
						trace.swap(left, right);
					}
				}
			}
			runs.push({ start, end });
			start = end;
		}
		if (runs.length === 1) return;
		for (let i = 0; i + 1 < runs.length; i += 2) {
			merge(trace, runs[i].start, runs[i].end, runs[i + 1].end);
		}
	}
}

/** Stable in-place merge using rotations; no auxiliary value array. */
function rotateMerge(trace: NumericTrace, start: number, middle: number, end: number) {
	let left = start;
	let right = middle;
	while (left < right && right < end) {
		if (trace.compare(left, right) <= 0) {
			left++;
			continue;
		}
		const value = trace.array[right];
		for (let index = right; index > left; index--) {
			trace.write(index, trace.array[index - 1]);
		}
		trace.write(left, value);
		left++;
		right++;
	}
}

export function inPlaceMergeSort(trace: NumericTrace) {
	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);
		trace.note(`Rotate-merge [${start}, ${middle}) and [${middle}, ${end})`);
		rotateMerge(trace, start, middle, end);
	}
	sort(0, trace.array.length);
}

/** Divide the merge at a median; independent child ranges form parallel tasks. */
export function parallelMergeSort(trace: NumericTrace) {
	function parallelMerge(
		source: number[],
		left: Run,
		right: Run,
		output: number,
		pivotFromLeft: boolean
	) {
		const leftSize = left.end - left.start;
		const rightSize = right.end - right.start;
		if (leftSize < rightSize) {
			parallelMerge(source, right, left, output, !pivotFromLeft);
			return;
		}
		if (leftSize === 0) return;
		const pivot = left.start + Math.floor(leftSize / 2);
		let low = right.start;
		let high = right.end;
		while (low < high) {
			const middle = low + Math.floor((high - low) / 2);
			const comparison = trace.compareValues(pivot, middle, source[pivot], source[middle]);
			if (pivotFromLeft ? comparison > 0 : comparison >= 0) {
				low = middle + 1;
			} else {
				high = middle;
			}
		}
		const destination = output + pivot - left.start + low - right.start;
		trace.write(destination, source[pivot], `Place parallel merge pivot ${source[pivot]}`);
		parallelMerge(
			source,
			{ start: left.start, end: pivot },
			{ start: right.start, end: low },
			output,
			pivotFromLeft
		);
		parallelMerge(
			source,
			{ start: pivot + 1, end: left.end },
			{ start: low, end: right.end },
			destination + 1,
			pivotFromLeft
		);
	}
	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);
		trace.note(`Fork-join merge of [${start}, ${middle}) and [${middle}, ${end})`);
		const source = [...trace.array];
		parallelMerge(source, { start, end: middle }, { start: middle, end }, start, true);
	}
	sort(0, trace.array.length);
}