Merge Sort in Javascript

The Merge Sort algorithm is a divide and conquer algorithm and its basic premise is to grab a problem that can be solved recursively and break it down into smaller chunks.  Then put the chunks back together and you will have a solution that grows higher than a linear solution but better than a quadratic solution.  This algorithm was discovered and applied a long time ago but I wrote my own version in JavaScript as a homework assignment for my Algorithms class.

Keep in mind that JavaScript has a sort method already!  It has been in place since ECS1 so this is not an attempt to improve on the solution – it is just an exercise.  I have also done some run time tests and will be plotting those results shortly.  I will also compare my run time results to the native JavaScript implementation (spoiler: the native implementation is faster!) and a Java version of the algorithm by Robert Sedgewick & Kevin Wayne.

The annotated JS code is below:

/* Merge Sort in Javascript by Carlos Moran */

//mergeSort gets two arrays and returns a sorted array

function mergeSort(A, B) {
    var s = A.length;
    var t = B.length;
    var u = s + t;

    var i = 0;
    var j = 0;

    // if only two values are to be compared then return the sorted array immediately

    var C = u == 2 ? (A[0] < B[0] ? [A[0], B[0]] : [B[0], A[0]]) : [];
    if(B[0]>A[0]) counter++;
    if (C.length > 0) return C.slice(0);

    //otherwise merge taking into account arrays that have different dimensions i.e. one array has 3 elements, one has 2
    for (var m = 0; m < u; m++) {

        if (j > (t - 1)) {
            C.push(A[i++]);
            counter++;
            continue;
        }
        if (i > (s - 1)) {
            C.push(B[j++]);
            continue;
        }

        A[i] <= B[j] ? C.push(A[i++]) : C.push(B[j++]);
        if(A[i]>B[j]) counter++;

    }

    return C.slice(0);

}

function splitArray(R) {

//split array in two
    var l = R.length;
    var n = ~~ (l / 2);

//merge recursively until smallest split is achieved then return merged array
    if (n > 0) {

        return mergeSort(splitArray(R.slice(0, n)), splitArray(R.slice(n)));
    } else {

        return mergeSort(R.slice(0, 1), R.slice(1));
    }

}

	return {ms: M[0], iterations: counter}; // return first array value and total operations
});

The test was run on Mocha on my desktop and the run times will be posted in a future post! Meanwhile, you can check my next post which runs a test suite of this algorithm in the browser.