CS Learning - Merge Sort - Iterative (Non Unique Items)

by Hari Menon

HTML

<pre>https://github.com/floydpink/computer-science-in-javascript/blob/master/algorithms/sorting/insertion-sort/insertion-sort.js
</pre>

<span>Size: </span>

<input type="text" name="size" id="size" value="90000"> <span>Max: </span>

<input type="text" name="size" id="maximum" value="100000">
<button id="generateAndSort">Generate &amp; Sort</button>
<br><pre id="output"></pre>

JavaScript

'use strict';

function setOutput(output) {
    document.querySelector('#output').innerHTML = output;
}

function generateLargeArray(size, max) {
    var array = [];
    while (array.length < size) {
        var randomNumber = Math.ceil(Math.random() * max);
        array.push(randomNumber);
    }
    return array;
}

function getCurrentTime() {
    return '\n' + new Date().toISOString() + '\n';
}

/**
 * Merges to arrays in order based on their natural
 * relationship.
 * @param {Array} left The first array to merge.
 * @param {Array} right The second array to merge.
 * @return {Array} The merged array.
 */
function merge(left, right){
    var result = [];

    while (left.length > 0 && right.length > 0){
        if (left[0] < right[0]){
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }

    result = result.concat(left).concat(right);
    
    //make sure remaining arrays are empty
    left.splice(0, left.length);
    right.splice(0, right.length);
    
    return result;
}

/**
 * Sorts an array in ascending natural order using
 * merge sort.
 * @param {Array} items The array to sort.
 * @return {Array} The sorted array.
 */
function mergeSort(items){

    // Terminal condition - don't need to do anything for arrays with 0 or 1 items
    if (items.length < 2) {
        return items;
    }

    var work = [],
        i,
        len;
        
        
    for (i=0, len=items.length; i < len; i++){
        work.push([items[i]]);
    }
    work.push([]);  //in case of odd number of items

    for (var lim=len; lim > 1; lim = Math.floor((lim+1)/2)){
        for (var j=0,k=0; k < lim; j++, k+=2){
            work[j] = merge(work[k], work[k+1]);
        }
        work[j] = [];  //in case of odd number of items
    }

    return work[0];
}

function sortArray(array) {
    return mergeSort(array);
}

document.querySelector('#generateAndSort').onclick = function () {
    var size =...