Floorplanner Tech Blog

Whenever I have a couple of minutes of spare time, I’m trying to learn more about algorithms . The first two algorithms were selection sort and insertion sort. Next up is merge sort. Merge sort is a bit different than selection and insertion sort. Selection and insertion sort are based on a loop inside a loop. That way you compare each value of a collection (one by one) to all the other values in the collection and sort them. Both in slightly different way. As you can imagine, sorting with a loop inside a loop isn’t very fast, Θ(n^2) to be precise. Merge sort attacks the problem in a different way. You could say that it’s based on the divide and conquer principal. It divides the problem in a bunch of tiny sub-problems, solves those problems and then combines them to get a result. The divide step isn’t that difficult. It takes a collection and splits it in two (equally sized) halves. This step is repeated until the smallest collection size is reached, 1. It uses a recursive function to accomplish this, a function that calls itself.

var collection = [5, 2, 4, 7, 1, 3, 2, 6];

divide(collection, 0, collection.length-1);

// a: collection, p: start index, r: end index
function divide(a, p, r) {
	if(p < r) {
		var q = Math.floor((p + r)/2); // calc middle of collection
		divide(a, p, q);
    		divide(a, q + 1, r);
		merge(a, p, q, r);
	}
}

The conquer step is a bit tricker. It’s based on a function that is able to merge two sorted collections into a new sorted collection.

function merge(a, p, q, r) {
	var n1 = q - p + 1;
	var left = [];
	for(var i = 0; i < n1; i++) {
		left.push(a[p + i]);
	}
        left.push(Infinity);

	var n2 = r - q;
	var right = [];
	for(var j = 0; j < n2; j++) {
		right.push(a[q + j + 1]);
	}
	right.push(Infinity);

	var i = 0;
	var j = 0;
	for(var k = p; k < r+1; k++) {
		if(left[i] 

So, the collection is first divided into sub-collections with the size of one. Those sub-collections are then merged together. That's done, step by step, by merging and sorting the small collections into a bigger collection. Combine collections with a size of one into sorted collections of a size of two, then combine them into sorted collections of 4 etc. until all sub-collections are merged.

Instead of having a loop inside a loop, you have a recursive divide function and a combining loop function. This results in a faster sorting than insertion or selection sort: Θ(nlgn).