Mergesort comparison count

mergesort_comparison_count.js

let count = 0;
/**
 * An implementation for Mergesort. Less efficient
 * than Quicksort. Again, you'd just use Array.sort
 * but if you found yourself unable to use that
 * there's always this option.
 *
 * Tests with:
 *
 * var array = [];
 * for(var i = 0; i < 20; i++) {
 *   array.push(Math.round(Math.random() * 100));
 * }
 *
 * Mergesort.sort(array);
 *
 * @author Paul Lewis
 */
var Mergesort = (function () {

    /**
     * Sorts the array by breaking it down
     * into smaller chunks.
     *
     * @param {Array} array The array to sort
     */
    function sort(array) {

        var length = array.length,
            mid = Math.floor(length * 0.5),
            left = array.slice(0, mid),
            right = array.slice(mid, length);

        if (length === 1) {
            return array;
        }

        return merge(sort(left), sort(right));

    }

    /**
     * Merges two sublists back together.
     * Shift either left or right onto
     * the result depending on which is
     * lower (assuming both exist), and simply
     * pushes on a list if the other doesn't
     * exist.
     *
     * @param {Array} left The left hand sublist
     * @param {Array} right The right hand sublist
     */
    function merge(left, right) {

        var result = [];

        while (left.length || right.length) {

            if (left.length && right.length) {

                count++;
                if (left[0] < right[0]) {
                    result.push(left.shift());
                } else {
                    result.push(right.shift());
                }

            } else if (left.length) {
                result.push(left.shift());
            } else {
                result.push(right.shift());
            }

        }

        return result;

    }

    return {
        sort: sort
    };

})();

function shuffle(array) {
    var currentIndex = array.length, temporaryValue, randomIndex;

    // While there remain elements to shuffle...
    while (0 !== currentIndex) {

        // Pick a remaining element...
        randomIndex = Math.floor(Math.random() * currentIndex);
        currentIndex -= 1;

        // And swap it with the current element.
        temporaryValue = array[currentIndex];
        array[currentIndex] = array[randomIndex];
        array[randomIndex] = temporaryValue;
    }

    return array;
}

const list = [1, 2];
for (let j = 0; j < 10; j++) {
    list.push(j + 2);
    const startTime = Date.now();
    for (let i = 0; i < 1000000; i++) {
        // new HeapSort(shuffle(list.slice(0))).main();
        Mergesort.sort(shuffle(list));
    }
    const endTime = Date.now();
    // Mergesort.sort(shuffle(list));
    console.log(`Random average for 1000000 loop with list size of ${list.length}: ${count / 1000000} (${endTime - startTime} ms)`);
    // console.log(count);
    count = 0;
}

/**
Random average for 1000000 loop with list size of 3: 2.667134 (513 ms)
Random average for 1000000 loop with list size of 4: 4.666111 (740 ms)
Random average for 1000000 loop with list size of 5: 7.333493 (1104 ms)
Random average for 1000000 loop with list size of 6: 9.933335 (1228 ms)
Random average for 1000000 loop with list size of 7: 12.770668 (1481 ms)
Random average for 1000000 loop with list size of 8: 15.734992 (1691 ms)
Random average for 1000000 loop with list size of 9: 19.200293 (2041 ms)
Random average for 1000000 loop with list size of 10: 22.723045 (2215 ms)
Random average for 1000000 loop with list size of 11: 26.341645 (2506 ms)
Random average for 1000000 loop with list size of 12: 30.00516 (2691 ms)
 */