Support in-place sort

[stephank]

Per @kriskowal's suggestion in #1.

See if we can add support for in-place sorting.

[stephank]

I'm not really up to speed on my sorting algorithms, so feel free to correct me on anything.

• StackOverflow and Wikipedia suggest that in-place merge-sort is less performant. (But of course, the current merge-sort is less memory efficient than alternatives.)
• Alternatives are difficult to adapt to become stable. (The same Wikipedia page mentions that for quicksort, 'stable in-place partitioning is more complex')
• The same Wikipedia also mentions this mystery article on an ideal algorithm, which I've yet to read.

/cc @kriskowal, @naneau

[Yaffle]

instead of implementing "in-place" variant, you can implement a sort, which modifies current array, but uses only one "new Array(length)" allocation, see http://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation

(function() {

// A stable array sort, because `Array#sort()` is not guaranteed stable.
// This is an implementation of merge sort, without recursion.

var stable = function(arr, comp) {
    if (typeof(comp) !== 'function') {
        comp = function(a, b) {
            return String(a).localeCompare(b);
        };
    }

    var len = arr.length;

    // Ensure we always return a new array, even if no passes occur.
    if (len <= 1) {
        return arr;
    }

    // Rather than dividing input, simply iterate chunks of 1, 2, 4, 8, etc.
    // Chunks are the size of the left or right hand in merge sort.
    // Stop when the left-hand covers all of the array.
    var buffer = new Array(len);
    var result = arr;
    for (var chk = 1; chk < len || result !== arr; chk *= 2) {
        pass(result, comp, chk, buffer);
        var tmp = result;
        result = buffer;
        buffer = tmp;
    }
    return arr;
};

// Run a single pass with the given chunk size. Returns a new array.
var pass = function(arr, comp, chk, result) {
    var len = arr.length;
    var i = 0;
    // Step size / double chunk size.
    var dbl = chk * 2;
    // Bounds of the left and right chunks.
    var l, r, e;
    // Iterators over the left and right chunk.
    var li, ri;

    // Iterate over pairs of chunks.
    for (l = 0; l < len; l += dbl) {
        r = l + chk;
        e = r + chk;
        if (r > len) r = len;
        if (e > len) e = len;

        // Iterate both chunks in parallel.
        li = l;
        ri = r;
        while (true) {
            // Compare the chunks.
            if (li < r && ri < e) {
                // This works for a regular `sort()` compatible comparator,
                // but also for a simple comparator like: `a > b`
                if (comp(arr[li], arr[ri]) <= 0) {
                    result[i++] = arr[li++];
                }
                else {
                    result[i++] = arr[ri++];
                }
            }
            // Nothing to compare, just flush what's left.
            else if (li < r) {
                result[i++] = arr[li++];
            }
            else if (ri < e) {
                result[i++] = arr[ri++];
            }
            // Both iterators are at the chunk ends.
            else {
                break;
            }
        }
    }
};

// Export using CommonJS or to the window.
if (typeof(module) !== 'undefined') {
    module.exports = stable;
}
else {
    window.stable = stable;
}

})();

[stephank]

I like this, also because it will save us allocations when not sorting in-place, only ever taking two. (And any scenario that previously used less than two allocations meant very small arrays any way.)

So I massaged the code a bit, and put up 0.1.4, with stable.inplace. Thanks!

[stephank]

Btw @Yaffle, I'm not sure how to credit you, so I simply did this: https://github.com/Two-Screen/stable/commit/c7a3520c5e276d45ac6e53007458f5aa4b74ef61

[Yaffle]

thanks