Async 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, completeFn, runTime, wait) {
    function defaultSort(a, b) {
        if ( a < b )
            return -1;
        if ( b < a )
            return 1;
        return 0;
    }
    
    function getTime() {
        if ( Date.now )
            return Date.now();
        else
            return new Date();
    }
    
    if ( 'undefined' === typeof sortFn || null === sortFn )
        sortFn = defaultSort;
    if ( 'undefined' === typeof runTime || null === runTime )
        runTime = 200;
    if ( 'undefined' === typeof wait || null === wait )
        wait = 200;
    
    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() {
        console.debug("starting...");
        var start = getTime();
        
        // Assumption: Incoming chunks are sorted (this is a merge sort)
        while ( chunkSize < array.length && getTime() - start < runTime ) {
            // Pick a processor
            if ( oneIdx < idx + chunkSize && twoIdx < idx + 2 * chunkSize && twoIdx < array.length )
                // Both chunks contain unprocessed entries
                processPair();
            else
  ...