Fast merge sort in JavaScript

Question

When developing a user interface that allows sorting by various different fields, I noticed that Array.prototype.sort() is extremely slow for large inputs. After some investigation, I found out that the problem was that my compare function was being called upwards of 8.5 million times for an input array of length 7500. If you ask me, that looks like \$O(n^2)\$ behavior. To address this, I decided to implement a merge sort.

Although I have tested my code and it appears to be working properly, it would still be helpful to have some other people look at it and see if there is more room for improvement or if it misbehaves in some subtle or pathological cases.

var mergesort = function (array, /* optional */ cmp) {
    /*
        Merge sort.
        On average, two orders of magnitude faster than Array.prototype.sort() for
        large arrays, with potentially many equal elements.
        Note that the default comparison function does not coerce its arguments to strings.
    */

    if (cmp === undefined) {
        // Note: This is not the same as the default behavior for Array.prototype.sort(),
        // which coerces elements to strings before comparing them.
        cmp = function (a, b) {
            'use asm';
            return a < b ? -1 : a === b ? 0 : 1;
        };
    }

    function merge (begin, begin_right, end) {
        'use asm';
        // Create a copy of the left and right halves.
        var left_size = begin_right - begin, right_size = end - begin_right;
        var left = array.slice(begin, begin_right), right = array.slice(begin_right, end);
        // Merge left and right halves back into original array.
        var i = begin, j = 0, k = 0;
        while (j < left_size && k < right_size)
            if (cmp(left[j], right[k]) <= 0)
                array[i++] = left[j++];
            else
                array[i++] = right[k++];
        // At this point, at least one of the two halves is finished.
        // Copy any remaining elements from left array back to original array.
        while (j < left_size) array[i++] = left[j++];
        // Copy any remaining elements from right array back to original array.
        while (k < right_size) array[i++] = right[k++];
        return;
    }

    function msort (begin, end) {
        'use asm';
        var size = end - begin;
        if (size <= 8) {
            // By experimentation, the sort is fastest when using native sort for
            // arrays with a maximum size somewhere between 4 and 16.
            // This decreases the depth of the recursion for an array size where
            // O(n^2) sorting algorithms are acceptable.
            var sub_array = array.slice(begin, end);
            sub_array.sort(cmp);
            // Copy the sorted array back to the original array.
            for (var i = 0; i < size; ++i)
                array[begin + i] = sub_array[i];
            return;
        }

        var begin_right = begin + (size >> 1);

        msort(begin, begin_right);
        msort(begin_right, end);
        merge(begin, begin_right, end);
    }

    msort(0, array.length);

    return array;
};

Answer 1

[...] it misbehaves in some subtle or pathological cases.

I may have identified a pathological case...

Caveat When Using Bitwise Shifting

This pertains to the following line:

var begin_right = begin + (size >> 1);

Using bitwise shifting to efficiently multiply or divide by a factor of two carries a risk when extremely large numbers are involved. size >> 1 will stop behaving predictably when size exceeds 2147483647.

This is fine if you don't expect to be sorting arrays of such magnitude, but you might as well double that range by using an unsigned bitwise shift (>>>), allowing you to shift any positive number up to 4294967295.

If you want to be safe with arrays even longer than that, you can use Math.floor(size/2) although that will negatively impact performance.

Here's a fiddle to demonstrate: http://jsfiddle.net/akxbLej5/1/