src/singletco.js

/**
 * Template for the recursive implementation of quicksort with explicit tail
 * call optimization.
 * This template allows to generate a specific version of the quicksort
 * algorithm for a certain partitioning algorithm.
 *
 * @param {callable} partition the implementation for the partitioning step
 */

export function singletco(partition) {
	/**
	 * Sorts interval [left,right) of the array parameter according to a
	 * compare method.
	 *
	 * @param {comparator} compare the comparator function
	 * @param {array} array random access array
	 * @param {offset} left inner left bound of the interval to sort
	 * @param {offset} right outer right bound of the interval to sort
	 *
	 */

	const sort = function (compare, array, left, right) {
		while (true) {
			// In the case where interval [left,right) contains
			// only one element we are done!

			if (right - left < 2) return;

			// Otherwise we partition interval [left,right) into three disjoint
			// subintervals [left,pivot), [pivot, pivot+1) and [pivot+1,right)
			// where the pivot is the position whose element
			// is greater or equal to all elements of the first subinterval
			// and less or equal to all elements of the third subinterval

			const pivot = partition(compare, array, left, right);

			// And then we just need to ask the recursion fairy
			// to sort the first and third subintervals

			// the recursion fairy sorts [left,pivot)
			sort(compare, array, left, pivot);

			// And then [pivot+1,right)
			left = pivot + 1;
		}
	};

	return sort;
}