Iterative Merge Sort

by Nick Iaconis

HTML

<fieldset>
    <legend>Input Generation:</legend>
    Number of sets: <input id="sets" /> Entries per set: <input id="entries" />
    <br />
    <button id="generate">Generate</button>
</fieldset>
Input: <br />
<textarea id="input" placeholder="[[...], ...]"></textarea>
<button id="go">Go</button>
<button id="random">Sample Input</button>
<br />
Output: <br />
<textarea id="output"></textarea>

CSS

textarea {
    width: 480px;
    height: 240px;
}

* {
    cursor: inherit;
}

JavaScript

function iterSort(array, context, sortFn) {
    function defaultSort(a, b) {
        if ( a < b )
            return -1;
        if ( b < a )
            return 1;
        return 0;
    }
    
    if ( 'undefined' === typeof sortFn || null === sortFn )
        sortFn = defaultSort;
    
    var idx = 0,
        chunkSize = 1,
        oneIdx = 0,
        twoIdx = 1,
        outIdx = 0,
        result = array.slice();
    
    function processPair() {        
        var cmp = sortFn.call(context, array[oneIdx], array[twoIdx]);
        
        if ( cmp < 0 ) {
            result[outIdx] = array[oneIdx];
            ++oneIdx;
        } else if ( cmp > 0 ) {
            result[outIdx] = array[twoIdx];
            ++twoIdx;
        } else {
            result[outIdx] = array[oneIdx];
            result[++outIdx] = array[twoIdx];
            ++oneIdx;
            ++twoIdx;
        }
        ++outIdx;
    }
    
    function processSingle() {
        if ( oneIdx < idx + chunkSize ) {
            result[outIdx] = array[oneIdx];
            ++oneIdx;
        } else {
            result[outIdx] = array[twoIdx];
            ++twoIdx;
        }
        ++outIdx;
    }
    
    function loopFn() {
        // Assumption: Incoming chunks are sorted (this is a merge sort)
        while ( chunkSize < array.length ) {
            // Pick a processor
            if ( oneIdx < idx + chunkSize && twoIdx < idx + 2 * chunkSize && twoIdx < array.length )
                // Both chunks contain unprocessed entries
                processPair();
            else
                // One chunk contains unprocessed entries
                processSingle();
        
            // Bounds check
            if ( outIdx === array.length ) {
                idx = 0;
                chunkSize = 2 * chunkSize;
                oneIdx = 0;
                twoIdx = chunkSize;
                outIdx = 0;
                array = result;
                result = array.slice();
            } else if (...