Heapsort
A well performing sort algorithm that uses a binary heap.
var heapsort = (function() { function exchange(array, i, j) { var temp = array[i]; array[i] = array[j]; array[j] = temp; } function maxHeapify(array, root) { var left = (root === 0) ? 1 : 2 * root, right = left + 1, largest = (left < array.heapSize && array[left] > array[root]) ? left : root; if (right < array.heapSize && array[right] > array[largest]) largest = right; if (largest !== root) { exchange(array, root, largest); maxHeapify(array, largest); } } function buildMaxHeap(array) { array.heapSize = array.length; for (var i = Math.round(array.length / 2); i >= 0; i--) { maxHeapify(array, i); update(array); } } return function(array) { buildMaxHeap(array); for (var i = array.length - 1; i >= 1; i--) { exchange(array, 0, i); array.heapSize--; maxHeapify(array, 0); update(array); } }; })();