Sort an array in place with heap sort and a comparator
A leaderboard service re-ranks large arrays of scores on a device with very little spare memory. It cannot afford a merge sort’s extra buffer, and it must never hit a quicksort’s O(n2) worst case. Heap sort fits both needs: O(n log n) comparisons in every case and O(1) extra space.
Implement heapSort(array, compare). It sorts array in place using heap sort and returns the same array.
heapSort(array, compare?) // => array (the same reference)
compare(a, b) works like the comparator of Array.prototype.sort: a negative number means a comes first, a positive number means b comes first, and 0 means either order is fine.compare is omitted, sort numbers in ascending numeric order ((a, b) => a - b). This differs from Array.prototype.sort, which compares strings by default.compare, so insertion sort or bubble sort will fail on large inputs.Array.prototype.sort or Array.prototype.toSorted.heapSort([42, 7, 19, 7, 3]);
// => [3, 7, 7, 19, 42]
heapSort([100, 9, 10, 1]);
// => [1, 9, 10, 100] (numeric, not [1, 10, 100, 9])
heapSort([2, 8, 5], (a, b) => b - a);
// => [8, 5, 2]
const players = [
{ name: 'Ana', points: 320 },
{ name: 'Bo', points: 950 },
{ name: 'Cy', points: 610 },
];
heapSort(players, (a, b) => b.points - a.points).map((p) => p.name);
// => ['Bo', 'Cy', 'Ana']
heapSort([]);
// => []
Store a binary max-heap inside the array itself: the children of index i are 2i + 1 and 2i + 2. Build the heap, then repeatedly swap the largest element to the end and shrink the heap by one.