There are four main steps in the merge sort algorithm (from Wikipedia):
- If the list is of length 0 or 1, then it is already sorted. Otherwise:
- Divide the unsorted list into two sublists of about half the size.
- Sort each sublist recursively by re-applying the merge sort.
- Merge the two sublists back into one sorted list.
I added a public mergeSort function to the sortArray object, which I showed in the first post in these series.
this.mergeSort = function() { elements = internalMergeSort(elements, this.onSort); return elements;};
This function calls the internalMergeSort function passing in the internal elements array and the onSort callback.
var internalMergeSort = function(elements, onSort){ if (elements.length < 2){ return elements; }
// Calculate the middle of the elementsvar middle = Math.floor(elements.length / 2);
// Divide var leftRange = elements.slice(0, middle);
var rightRange = elements.slice(middle, elements.length);
// Conquer var mergingResult = merge(internalMergeSort(leftRange, onSort),
internalMergeSort(rightRange, onSort));
onSort(mergingResult);
return mergingResult;};
The function recursively divides the elements in two parts, sorting them and finally merging them back together.
The merge function is implemented like this.
function merge(left, right){ var res = [];
while (left.length > 0 && right.length > 0) { if (left[0] <= right[0]) {res.push(left.shift());
} else {res.push(right.shift());
}
}
while (left.length > 0) { res.push(left.shift());
}
while (right.length > 0) { res.push(right.shift());
}
return res;};
I peeked at this implementation, which is very similar to mine and which helped me write the first while loop more elegantly.
Testing sorting algorithms is pretty easy. So far, I have only defined one QUnit test for this algorithm.
test("MergeSort sorts.", function() { var sortArray = new algorithms.sortArray();sortArray.push(15);
...
sortArray.push(130);
var actual = sortArray.mergeSort();
var expected = [1, 10, 12, 15, 17, 22, 25, 50, 60, 90, 130];
deepEqual(actual, expected);
});
A small remark here is that you should use deepEqual instead of equal for array assertions. We want to compare the contents of the array, not their references.
See the algorithm in action here.
