array.prototype.sort.js

function min(left, right) {
    if (left < right) {
        return left;
    }
    return right;
}
function sortMerge(dst, src, srcIndex, srcEnd, width, comparator) {
    "use strict";

    var left = srcIndex;
    var leftEnd = min(left + width, srcEnd);
    var right = leftEnd;
    var rightEnd = min(right + width, srcEnd);

    for (var dstIndex = left; dstIndex < rightEnd; ++dstIndex) {
        if (right < rightEnd) {
            if (left >= leftEnd) {
                dst[dstIndex] = src[right];
                ++right;
                continue;
            }

            var comparisonResult = comparator(src[right], src[left]);
            if (comparisonResult === false || comparisonResult < 0) {

                dst[dstIndex] = src[right];
                ++right;
                continue;
            }

        }

        dst[dstIndex] = src[left];
        ++left;
    }
}


function sortMergeSort(array, comparator) {
    "use strict";

    var valueCount = array.length;
    var buffer = new Array(valueCount);

    var dst = buffer;
    var src = array;
    for (var width = 1; width < valueCount; width = width * 2) {
        for (var srcIndex = 0; srcIndex < valueCount; srcIndex = srcIndex + 2 * width)
            sortMerge(dst, src, srcIndex, valueCount, width, comparator);

        var tmp = src;
        src = dst;
        dst = tmp;
    }

    return src;
}

function sortStringComparator(a, b) {
    "use strict";

    var aString = a.string;
    var bString = b.string;

    if (aString === bString)
        return 0;

    return aString > bString ? 1 : -1;
}

function sortBucketSort(array, dst, bucket, depth) {
    "use strict";

    if (bucket.length < 32 || depth > 32) {
        var sorted = sortMergeSort(bucket, sortStringComparator);
        for (var i = 0; i < sorted.length; ++i) {
            array[dst] = sorted[i].value;
            ++dst;
        }
        return dst;
    }

    var buckets = [];
    for (var i = 0; i < bucket.length; ++i) {
        var entry = bucket[i];
        var string = entry.string;
        if (string.length == depth) {

            array[dst] = entry.value;
            ++dst;
            continue;
        }

        var c = string[depth];
        var cBucket = buckets[c];
        if (cBucket)
            cBucket.push(entry);
        else
            buckets[c] = [entry];
    }

    for (var i = 0; i < buckets.length; ++i) {
        if (!buckets[i])
            continue;
        dst = sortBucketSort(array, dst, buckets[i], depth + 1);
    }

    return dst;
}


function sortCommit(receiver, receiverLength, sorted, undefinedCount) {
    "use strict";

    // Move undefineds and holes to the end of an array. Result is [values..., undefineds..., holes...].

    var sortedLength = sorted.length;

    var i = 0;

    for (; i < sortedLength; ++i)
        receiver[i] = sorted[i];

    for (; i < sortedLength + undefinedCount; ++i)
        receiver[i] = undefined;

    for (; i < receiverLength; ++i)
        delete receiver[i];
}
function sortCompact(receiver, receiverLength, compacted, isStringSort) {
    "use strict";

    var undefinedCount = 0;
    var compactedIndex = 0;

    for (var i = 0; i < receiverLength; ++i) {
        if (i in receiver) {
            var value = receiver[i];
            if (value === undefined)
                ++undefinedCount;
            else {
                if (isStringSort) {
                    compacted[compactedIndex] = {
                        string: toString(value),
                        value: value
                    }
                } else {
                    compacted[compactedIndex] = value;
                }

                ++compactedIndex;
            }
        }
    }

    return undefinedCount;
}

Array.prototype.sort = function (comparator) {
    "use strict";

    var isStringSort = false;
    if (comparator === undefined)
        isStringSort = true;

    var receiver = ___toObject(this, "Array.prototype.sort requires that |this| not be null or undefined");
    var receiverLength = ___toLength(receiver.length);

    // For compatibility with Firefox and Chrome, do nothing observable
    // to the target array if it has 0 or 1 sortable properties.
    if (receiverLength < 2)
        return receiver;

    var compacted = [];
    var sorted = null;
    var undefinedCount = sortCompact(receiver, receiverLength, compacted, isStringSort);
    if (isStringSort) {
        sorted = new Array(compacted.length);
        sortBucketSort(sorted, 0, compacted, 0);
    } else
        sorted = sortMergeSort(compacted, comparator);
    sortCommit(receiver, receiverLength, sorted, undefinedCount);
    return receiver;
}