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;};
Fast merge sort in JavaScript
javascript;mergesort