Promise Sort: The First Truly Asynchronous Quicksort Algorithm!

promise_sort.js

PromiseSort = {
    pivotIndexMedian: function (ary, pred, startIndex, endIndex) {
        var midIndex = Math.floor((startIndex + endIndex) / 2),
            indexes = [startIndex, midIndex, endIndex];
        return indexes.sort(function (i, j) {
            return pred(ary[i], ary[j]);
        })[1]; // return median index
    },
    pivotIndexRandom: function (_ary, _pred, startIndex, endIndex) {
        return Math.floor(Math.random() * (endIndex - startIndex + 1)) + startIndex;
    },
    pivotIndex: function (ary, pred, startIndex, endIndex) {
        return PromiseSort.pivotIndexMedian(ary, pred, startIndex, endIndex);
    },
    swap: function (ary, i, j) {
        var t = ary[i];
        ary[i] = ary[j];
        ary[j] = t;
    },
    partition: function (ary, pred, startIndex, endIndex) {
        var pivotIndex = PromiseSort.pivotIndex(ary, pred, startIndex, endIndex);
        PromiseSort.swap(ary, startIndex, pivotIndex);
        var i = startIndex + 1;
        for (var j = startIndex + 1; j <= endIndex; j = j + 1) {
            if (pred(ary[j], ary[startIndex]) < 0) {
                PromiseSort.swap(ary, i, j);
                i = i + 1;
            }
        }
        PromiseSort.swap(ary, startIndex, i - 1);
        return i;
    },
    quickInnerInsertions: function (ary, pred, startIndex, endIndex) {
        for (var i = startIndex + 1; i <= endIndex; i = i + 1) {
            var t = ary[i];
            var j = i - 1;
            while (j >= startIndex && pred(ary[j], t) > 0) {
                ary[j + 1] = ary[j];
                j = j - 1;
            }
            ary[j + 1] = t;
        }
    },
    quickInner: function (ary, pred, startIndex, endIndex) {
        var length = endIndex - startIndex + 1;
        if (length > 1) {
            if (length <= 100) {
                PromiseSort.quickInnerInsertions(ary, pred, startIndex, endIndex);
            } else {
                var i = PromiseSort.partition(ary, pred, startIndex, endIndex);
                if (i <= length / 2 - 1) {
                    PromiseSort.quickInner(ary, pred, startIndex, i - 2),
                    PromiseSort.quickInner(ary, pred, i, endIndex);
                } else {
                    PromiseSort.quickInner(ary, pred, i, endIndex),
                    PromiseSort.quickInner(ary, pred, startIndex, i - 2);
                }
            }
        }
    },
    Deferred: $.Deferred,
    when: $.when,
    nextTick: function (callback) {
        setTimeout(callback, 0);
    },
    inner: function (ary, pred, startIndex, endIndex) {
        var deferred = PromiseSort.Deferred();
        var length = endIndex - startIndex + 1;
        if (length <= 1) {
            deferred.resolve(ary);
        } else if (length < 100000) {
            PromiseSort.quickInner(ary, pred, startIndex, endIndex);
            deferred.resolve(ary);
        } else {
            PromiseSort.nextTick(function () {
                var i = PromiseSort.partition(ary, pred, startIndex, endIndex);
                var promiseLeft = PromiseSort.inner(ary, pred, startIndex, i - 2),
                    promiseRight = PromiseSort.inner(ary, pred, i, endIndex);
                PromiseSort.when(promiseLeft, promiseRight).done(function () {
                    deferred.resolve(ary);
                });
            });
        }
        return deferred.promise();
    },
    mutable: function (ary, pred) {
        return PromiseSort.inner(ary, pred, 0, ary.length - 1);
    },
    immutable: function (ary, pred) {
        return PromiseSort.mutable(ary.slice(0), pred);
    }
};

/*
function compare(a, b) {
    return a - b;
}
function printArray(ary) {
    var str = '[' + ary.join(',') + ']';
    console.log(str);
}
PromiseSort.immutable([], compare).done(printArray);
PromiseSort.immutable([42], compare).done(printArray);
PromiseSort.immutable([42, 1], compare).done(printArray);
PromiseSort.immutable([3, 1, 2], compare).done(printArray);
PromiseSort.immutable([5, 4, 3, 2, 1], compare).done(printArray);
PromiseSort.immutable([9, 666, 2, 1, 9, 3, 5, 6, 9, 7, 8, 4], compare).done(printArray);
*/

Results:

http://jsfiddle.net/marshall_lee/Dt5sa/embedded/result,js/
http://jsfiddle.net/marshall_lee/Dt5sa/