An implementation of the well-known insertion sort algorithm with search space partitioning (aka binary space partitioning)

sorting.js

/**
 * Sort a sequence using the binary insertion sort algorithm.
 *
 * The traditional insertion sort algorithm will look for a place to re-insert "current" element by simply walking towards the beginning of the sequence, through the already sorted portion. This implementation drastically reduces number of comparisons thus required to determine where in the [already sorted] portion of the sequence to re-insert current element, by using so-called binary space/search partitioning. This yields a worst-case `n * Math.log2(n)` performance vs traditionally `n * n`, all the more noticable for large enough sequence and/or where cost of sorting order comparison (see the `fn` parameter) is non-negligible.
 *
 * The sequence is sorted in-place, which is why this procedure does not return anything. Sorting is guarateed to be "stable" -- any two items for which `compare` does not indicate sorting (by returning zero), retain their relative positions in the sequence. Worst case performance is, unlike regular insertion sort, `O(n * Math.log2(n))` where `n` is the length of sequence.
 *
 * @param items The sequence to sort; the sequence must be "subscriptable" through zero-indexed property access (i.e. like an array), have a `length` property that, much like with an array, returns the number of items in the sequence, and have a `move` method taking two numeric indices `i` and `j` for parameters, where the former identifies the item to remove from its original position in the sequence, and the latter identifies the position at which to re-insert the [removed] item; value of `i` is guaranteed to never be a smaller number than `j`
 * @param {function} compare A function to use for comparing items in the sequence to one another to determine relative sorting order; any two arbitrary items may be passed to `compare`; the semantics of the function are identical to the one used with `Array.prototype.sort`;
 */
export function insertion_sort(items, compare) {
	for(let l = items.length, i = 0; i != l; i++) {
		let b = 0, u = i; /// `b` stands for "base", the lower bound of the already sorted portion of the sequence, beyond which items are known to sort _before_ candidate (`items[i]`); `u` stands for "upper" -- the upper bound of the already sorted portion of the sequence, beyond which items are known to sort _after_ or are equal (see "stable sorting") to the candidate
		do { /// The loop slices search space in half for every iteration, trying to find the item just before which to re-insert the candidate
			const p = (b + u) >> 1;
			if(compare(items[i], items[p]) >= 0) b = p;
			else u = p;
		} while((u - b) > 1); /// Once the partition is small enough we already know where to insert, we break the loop.
		items.move(i, u); /// And invoke `move` expecting it to re-insert `items[i]` into position `u`.
	}
}