Testing Merge Sort with Jasmine

When designing algorithms you are looking to get the correct results in the least number of steps possible.  The running time of an algorithm is part of the analysis of any algorithm.  A key question in this analysis is:  When your data set grows what happens to the run time of your solution? For that reason I am running my algorithm class homework solutions through test runners and I’ll post them here.

A few observations during this process :

• It’s generally better to run these tests on the command line.  Making a test suite run within a blog post has its challenges.
• You’re probably more interested in the results than in me figuring out how to do this within the confines of a blog post.
• Hence, in future posts I will probably post the code for a Node JS set-up and not for the browser.
• I used Jasmine JS which is very nice and easy to use and it does provide test results.  However, I did make the mistake of running a failing spec on a 100k entry array which yielded 100k errors and crashed my browser!
• I used a 100k array for the run time to be observable.  To make my life easier I will run several tests off the browser and instead post a chart of the results.
• I was curious to see how long it takes to sort a large array in the browser.  Why did I want to see this happen? I don’t know.

The Merge Sort code is here (in my previous post).

In order to run the algorithm on this page I decided to load a file with random entries.  The code for the load uses the jQuery Ajax function.  It’s very straightforward to set up.  In the txt file, each line is a new entry.  Hence, the success function creates an array by doing a split on the regexp: /\n|\r\n|\r/ which is just matching a new line.  Each entry is then forced to be an integer.

	$.ajax({
        type: "GET",
        url: "./jslib/IntegerArray.txt",
        dataType: "text",
        success: function (data) {

        	var array = data.split(/\r\n|\r|\n/);
        	for(var i =0; i<array.length; i++) {
        		array[i] = parseInt(array[i]);
        	}
        	A = array.slice(0);

        }

    }).done(function(){ 
    	console.log("loaded"); 
    	runSpec();
    });

When the load is complete, the runSpec function is called.  This is the test suite for Jasmine.  I run four tests:

1. Make sure the length of the array is 100k
2. Call Merge Sort and make sure every item in the array is in ascending order.
3. Call JavaScript sort and make sure every item in the array is in ascending order.
4. Verify that the native (JavaScript) sort if faster.

The test suite is below:

describe("Load file",function(){

			it("Should split into array correctly", function(){

				expect(A.length).toBe(100000);

			});

		});

		describe("Items should be sorted", function(){
			it("It is sorted if all items are in ascending order", function(){
				mst = new Date();
				M = splitArray(A);
				met = new Date();
				for (var n=0; n<M.length-1; n++) {
					expect(M[n]).toBeLessThan(M[n+1]);
				}
			});
		});

		describe("JavaScript Sort", function(){
			it("It is sorted if all items are in ascending order", function(){
				nst = new Date();
				X = A.sort(function(a,b) { return a-b; });
				net = new Date();
				for (var n=0; n<X.length-1; n++) {
					expect(X[n]).toBeLessThan(X[n+1]);
				}
			});
		});

		describe("Native vs Merge Sort", function () {
			it("Native sort should be quicker", function(){

				expect(net-nst).toBeLessThan(met-mst);

			});
		});

All those tests are run on this post.  So keep scrolling down to see the Jasmine Spec runner test output!

Test is running …. Jasmine test runner will load shortly at the bottom of the screen…

Run time Summary:

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.