The algorithm has an average time complexity of O(n log n), where n is the size of the input array.

Heap Sort in JavaScript.js

/**
 * Sorts an array using the heapsort algorithm.
 * Heapsort is a comparison-based sorting algorithm.
 * Heapsort is an improved selection sort consisting of the use of a
 * heap data structure instead of a linear-time search to find the maximum or minimum element.
 *
 * @param {Array} arr - The array to be sorted.
 * @return {Array} - The sorted array.
 */
function heapsort(arr) {
    const a = [...arr];
    let l = a.length;

    const heapify = (a, i, l) => {
        const left = 2 * i + 1;
        const right = 2 * i + 2;
        let max = i;
        if (left < l && a[left] > a[max]) max = left;
        if (right < l && a[right] > a[max]) max = right;
        if (max !== i) {
            [a[max], a[i]] = [a[i], a[max]];
            heapify(a, max, l);
        }
    };

    for (let i = Math.floor(l / 2); i >= 0; i -= 1) heapify(a, i, l);
    for (let i = a.length - 1; i > 0; i--) {
        [a[0], a[i]] = [a[i], a[0]];
        l--;
        heapify(a, 0, l);
    }
    return a;
}

heapsort([6, 3, 4, 1]); // [1, 3, 4, 6]