Insertion sort in JS

cachedComparator.js

/**
 * Augments a sort function with a bi-map cache. Useful if the comparison is costly.
 * @param {SortFunction} comparator
 * @returns {SortFunction}
 */
export function cachedComparator (comparator) {
  const cache = new Map();

  return (a, b) => {
    let result;

    if (cache.has(a)) {
      const cacheA = cache.get(a);

      if (cacheA.has(b))
        return cacheA.get(b);

      result = comparator(a, b);

      cacheA.set(b, result);
    } else {
      result = comparator(a, b);

      cache.set(a, new Map([
        [ b, result ]
      ]));
    }
    // Store the opposite comparison
    if (cache.has(b)) {
      const cacheB = cache.get(b);

      if (!cacheB.has(a))
        cacheB.set(a, -result);
    } else {
      cache.set(b, new Map([
        [ a, -result ]
      ]));
    }

    return result;
  };
}

insertionSort.js

/**
 * A comparison sort function that returns:
 * - a negative number if `a` comes before `b`;
 * - a positive number if `a` comes after `b`;
 * - 0 if `a` and `b` are considered equal.
 * @callback SortFunction
 * @param a
 * @param b
 * @returns {number}
 */

/**
 * On-line insertion sort of any finite iterable sequence.
 *
 * @param {Iterable} it
 * @param {SortFunction} [comparator]
 * @returns {Array}
 */
export function insertionSort (it, comparator = (a, b) => a - b) {
  it = it[Symbol.iterator]();

  const res = [];
  const firstIteration = it.next();

  if (firstIteration.done)
    return [ firstIteration.value ];

  const firstEntry = firstIteration.value;
  const secondIteration = it.next();
  const secondEntry = secondIteration.value;

  const firstComparison = comparator(firstEntry, secondEntry);

  let minYet,
      maxYet;

  if (firstComparison <= 0) {
    minYet = firstEntry;
    maxYet = secondEntry;
  }
  else {
    minYet = secondEntry;
    maxYet = firstEntry;
  }

  res.push(minYet, maxYet);

  if (secondIteration.done)
    return res;

  for (const entry of it) {
    if (comparator(entry, minYet) < 0) {
      res.unshift(entry);
      minYet = entry;
      continue;
    }
    if (comparator(entry, maxYet) >= 0) { // Stable sorting with >=
      res.push(entry);
      maxYet = entry;
      continue;
    }

    const { length } = res;

    for (let i = 1; i < length; ++i) {
      const lastI = length - i;
      const sortedFirstEntry = res[i],
            sortedLastEntry = res[lastI];

      if (comparator(entry, sortedFirstEntry) < 0) {
        // Put the new entry before the one considered greater
        res.splice(i, 0, entry);
        break;
      }
      // The more in the middle the new entry should be, the worse this code affects performance.
      // If you have prior knowledge of how the data is sorted, consider commenting this block
      if (comparator(entry, sortedLastEntry) >= 0) {
        // Put the new entry after the one considered lesser/equal
        res.splice(lastI + 1, 0, entry);
        break;
      }
    }
  }

  return res;
}

// Use
insertionSort([ 4, 9, 12, 7, 0 ]);
insertionSort("At night I sleep Zzz", new Intl.Collator("en", { sensitivity: "accent"}).compare);