Implement a stable, recursive top-down merge sort with compare
A leaderboard sorts players by score, but players who tie must stay in the order they finished, which the server already sent. That needs a stable sort, and the team wants one whose cost is predictable: merge sort never needs more than about n log n comparisons, whatever the input looks like.
Implement mergeSort(items, compare) with a recursive, top-down merge sort. It returns a new sorted array.
mergeSort(items, compare?) // => new array, sorted
compare(a, b) works like the callback of Array.prototype.sort: a negative number means a comes first, a positive number means b comes first, and 0 means they tie.compare, order with < and >: numbers numerically (so 10 comes after 9), strings by code unit.items.items. Always return a new array, even for zero or one item.compare at most n × ⌈log2 n⌉ times for n items. A correct merge sort stays under this limit; insertion or selection sort does not.Array.prototype.sort or Array.prototype.toSorted.mergeSort([38, 5, 10, 9, -2]);
// => [-2, 5, 9, 10, 38]
mergeSort(['pear', 'Fig', 'apple']);
// => ['Fig', 'apple', 'pear'] ('F' sorts before lowercase letters)
const finishers = [
{ name: 'Ana', score: 90 },
{ name: 'Bo', score: 75 },
{ name: 'Cy', score: 90 },
{ name: 'Di', score: 75 },
];
mergeSort(finishers, (a, b) => b.score - a.score).map((p) => p.name);
// => ['Ana', 'Cy', 'Bo', 'Di'] (ties keep finishing order)
mergeSort([]); // => []