Merge Sort

Continuing to evaluate efficient sorting algorithms, today we’ll look at merge sort. Merge sort[1] is a comparison sort using a divide and conquer algorithm, developed by John von Neumann[2] in 1945. It recursively divides the list into smaller sublists of length one, then repeatedly merges the sublists in order until there is only one sublist left. It has a worst case runtime of (O(nlogn)), making it worst-case more efficient than Quicksort.

How do it…

Merge sort needs two functions, the first is a function to merge two ordered
arrays together:

function fnMerge(aLeft, aRight){
	var aResult = [],
		iLeft = 0,
	    iRight = 0;

	// iterate until one array is empty
	while (iLeft < aLeft.length && iRight < aRight.length) {
		// push the next ordered value on the resulting array
		// and increment its counter
		if (aLeft[iLeft] < aRight[iRight]) {
			aResult.push(aLeft[iLeft++]);
		}
		else {
			aResult.push(aRight[iRight++]);
		}
	}

	// join any remaining values from the two arrays into the results array
	return aResult.concat(aLeft.slice(iLeft)).concat(aRight.slice(iRight));
}

The second function is the public merge sort function that recursively splits the array into smaller halves before calling the merge function:

function fnMergeSort(aList) {
	// zero or 1 length arrays are already sorted
	if (2 > aList.length) {
		return aList;
	}

	var iMiddle = Math.floor(aList.length / 2);
	return fnMerge(
        fnMergeSort(aList.slice(0, iMiddle)),
        fnMergeSort(aList.slice(iMiddle)));
}

This visual is a little harder, but it shows each step of the splitting and merging functions:


Restart merge sort With a New Array

If we take a 10,000 element array and sort it, here is how merge sort compares to native array sort (prints to the console):

Merge sort Comparison Tests

How it works…

The merge sort algorithm recursively breaks the array into smaller subarrays by splitting the arrays in half, until all subarrays are length one or zero. By their nature (having only one or zero element), these subarrays are sorted. The algorithm then recursively merges the sub arrays together in order. As each subarray is combined the new subarray is ordered from the two merging subarrays, resulting eventually in one final sorted array. Since the same steps need to be taken regardless of how sorted the original array was, merge sort has an average, best, and worst case runtime of O(nlogn).

The merging function accepts two sorted subarrays and merges them together into a new sorted array. We solve this by iterating until one array is fully merged, using index trackers on each array, and inserting the greater value into the merged array on each iteration. Since both lists are in order, we know that when the iteration stops, all uncompared elements in the second array are greater than the already joined elements, so we can just concatenate the remaining elements at the end[3]. Rather than using an if statement to concatenate the right subarray, we just concatenate the remaining elements of both arrays, so the fully merged array will concatenate zero elements, and the other will concatenate all unmerged elements.

The merge sort function accepts a single array and splits it into two relatively even subarrays (if the array has an odd length, one subarray may be an element larger than the other). Those subarrays are each passed to the merge sort function and the results of the recursive merge sorts are joined using the merge function. Thus eventually, returning a single sorted array. The recursive calls stop when the subarrays are all of length one or zero.

There’s more…

If it is important that your merge sort function modifies the passed in array, you can use the following technique to splice the new elements into the original array[3]:

function fnMergeSort(aList) {
    // zero or 1 length arrays are already sorted
    if (2 > aList.length) {
        return aList;
    }

    var iMidIndex = Math.floor(aList.length / 2);
    var aParams = fnMerge(
        fnMergeSort(aList.slice(0, iMidIndex)),
        fnMergeSort(aList.slice(iMidIndex)));

    // put arguments one and two of the splice function into the
    // front of aParams, remaining arguments are elements to splice in
    aParams.unshift(0, aList.length);
    aList.splice.apply(aList, aParams);
}

Here we’ve used the splice function to replace all the elements in the provide array with the sorted elements, so that the originally provided list is modified, instead of returning a new sorted array. The signature of the splice function is the start index, the length to splice, and any number of elements to insert to replace the range we are splicing over. As such, we unshift the start index and length for the splice to the front of the array of sorted elements, so that we can use the apply function to properly pass everything into the splice function, which has a signature startIndex, lengthOfSplice, firstElementToSpliceIn, …, nthElementToSpliceIn.

References

  1. Merge sort Wikipedia article
  2. John von Neumann
  3. Computer science in JavaScript: Merge sort

Quicksort

We’ve looked a variety of in-efficient sorting algorithms, today we’ll look at Quicksort (aka. partition exchange sort), as a first foray into faster and more frequently used sorting algorithms. Quicksort[1] is a comparison sort using a divide and conquer algorithm, developed by Tony Hoare[2] in 1960. It recursively divides the list into smaller lists around a pivot value and sorts them, which means much smaller data sets when actually sorting. It has a ...

Selection Sort

Continuing our sorting algorithm discussion, today’s article will cover a technique known as Selection Sort. Selection sort is a simple, quadratic (O(n2)) in-place comparison sort algorithm that divides the array into two lists: an already sorted part and a to-sort part. The algorithm moves for through the array and inserts the next value in-place by searching the unsorted part of the array for the next value. In practice, the selection sort is useful when memory ...

Insertion Sort

Continuing our sorting algorithm discussion, today’s article will cover a technique known as Insertion Sort. Insertion sort[1] is a simple, quadratic (O(n2)) sorting algorithm that iterates forward through the array, sorting the current index value in-place by inserting it into the correct position among the values at smaller indices, which were sorted in previous passes. In practice it out performs the other quadratic sorting algorithms, such as Bubble Sort and Selection Sort. ...

Bubble Sort

This is the first article in an educational series covering various sorting techniques. The goal is to cover many of the popular sorting techniques, starting with the easiest to understand, and building up to a discussion about the strategies used by popular JavaScript engines to optimize the sort function of Array. Today’s article will cover bubble sort. Bubble sort is a simple sorting algorithm that repeatedly steps through a list, comparing each pair of adjacent ...