Stable in-place insertion sort with optional comparator
A live leaderboard re-sorts its rows after every score update. Between updates only a player or two moves, so the list is almost always nearly sorted. Insertion sort shines here: it does almost no work on input that is already in order, and it never reorders rows with equal scores.
Implement insertionSort(array, compare). It sorts array in place with insertion sort and returns the same array.
insertionSort(array, compare?) // => array (the same instance, now sorted)
compare(a, b) works like the Array.prototype.sort comparator: a negative number if a goes before b, a positive number if a goes after b, and 0 if they are equal.compare is omitted, sort ascending with < and >. Numbers compare as numbers (9 before 10) and strings by code unit ('Z' before 'a'). This is not the default of Array.prototype.sort, which compares numbers as strings.1. Take the current element and compare it with the elements to its left, nearest first, by calling compare(left, current).0 or negative, or when you reach the start. Then put the current element in the gap.n elements uses exactly n - 1 comparisons, and a reversed array of 5 distinct elements uses exactly 10.array in place and return it (not a copy).Array.prototype.sort or Array.prototype.toSorted.compare.insertionSort([5, 2, 9, 1, 5, 6]); // => [1, 2, 5, 5, 6, 9]
insertionSort([10, 9, 100, -5, 0]); // => [-5, 0, 9, 10, 100]
insertionSort(['pear', 'apple', 'Fig']); // => ['Fig', 'apple', 'pear']
insertionSort([3, 1, 2], (a, b) => b - a); // => [3, 2, 1]
const rows = [
{ name: 'Ana', score: 40 },
{ name: 'Ben', score: 55 },
{ name: 'Cy', score: 40 },
];
insertionSort(rows, (a, b) => b.score - a.score);
// => Ben (55), Ana (40), Cy (40): Ana stays ahead of Cy