26 Jul 2011

Merge sorting in JavaScript

The latest addition to my [data structures and algorithms in JavaScript](https://github.com/JefClaes Data-structures-and-algorithms-in-JavaScript) is the merge sort algorithm.

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 found it a lot easier to understand the algorithm by just looking at this diagram (also from Wikipedia).

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 elements
    var 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.

code

Jef Claes

Merge sorting in JavaScript