written live, don't trust

sorting.js

/*
 * Keeps a portion of the array sorted at all time,
 * called the invariant.
 *
 * Every time you try to sort a new element, you cmpare
 * against all the elems in the invariant, and put it in
 * its right place.
 *
 * Keep doing this until the size invariant array = size orginal
 * array.
 */

function insertionSort(array){
    // assume invariant is the first element, and thus is already
    // sorted

    for(var i = 1; i < array.length; i++){
        var k = i - 1;

        while(array[i] < array[k] && k >= 0){
            var tmp = array[k];
            array[k] = array[i];
            array[i] = tmp;
            k--;
            i--;
        }
    }

    return array;
}

/*
 * First, break the array down until its either 2 or 1 element in size
 * We sort these small arrays and recurively merge them in linear time
 * return the result.
 *
 */

function mergeSort(array){
    if(array.length <= 3){
        return insertionSort(array);
    }

    var split = Math.round(array.length/2),
        rhs = array.slice(0, split);
        lhs = array.slice(split, array.length);

    rhs = mergeSort(rhs);
    lhs = mergeSort(lhs);

    var k = 0,
        j = 0;

    for(var i = 0; i < array.length; i++){
        if(rhs[k] < lhs[j]){
            array[i] = rhs[k];
            k++;
        }else{
            array[i] = lhs[j];
            j++;
        }
    }

    return array;
}

console.log(mergeSort([5, 4, 21, 1]));