Data Structures and Algorithms Show (5): Merge Sort

$scope.mergeSortTopDown = function(list) {
    // return the one element array as a recursive exising condition.
    if(list.length < 2){
        return list;
    }
    var middle = Math.floor(list.length / 2);
    var left = list.slice(0, middle);
    var right = list.slice(middle, list.length);
    // continue to split into two sub arrays in a recursive way.
    left = $scope.mergeSortTopDown(left);
    right = $scope.mergeSortTopDown(right);
    var retList = [];
    var i = 0;
    var j = 0;
    // concat two sub arrays together in order.
    while(i < left.length && j < right.length){
        if(left[i] <= right[j]){
            retList.push(left[i]);
            i++;
        }else{
            retList.push(right[j]);
            j++;
        }
    }
    // if there is more elements left in left sub array.
    while(i < left.length){
        retList.push(left[i++]);
    }
    // if there is more elements left in right sub array.
    while(j < right.length){
        retList.push(right[j++]);
    }
    console.log(retList);
    return retList;
}

$scope.mergeSortBottomUp = function(list){
    var step = 1;
    var pos = 0;
    while(step < list.length){
        while(pos < list.length){
            $scope.mergeCompare(list, pos, step);
            pos += step * 2;
            console.log(list);
        }
        pos = 0;
        step *= 2;
    }
}

$scope.mergeCompare = function(list, pos, step){
    var left = list.slice(pos, pos + step);
    var right = list.slice(pos + step, pos + step * 2);
    var i = 0;
    var j = 0;
    var k = pos;
    while(i < left.length && j < right.length){
        if(left[i] <= right[j]){
            list[k++] = left[i++];
        }else{
            list[k++] = right[j++];
        }
    }
    // if there is more elements left in left sub array.
    while(i < left.length){
        list[k++] = left[i++];
    }
    // if there is more elements left in right sub array.
    while(j < right.length){
        list[k++] = right[j++];
    }
}

Last time we already knew the secret of one of the advanced sort algorithms, Shell Sort. Basing on Insertion Sort make Shell Sort a little bit more complicated than those simple sort algorithms but more efficient. Nevertheless, finding a best gaps array is not a easy task, which cause a rare application of Shell Sort. So, let us move onto another advanced sort method, Merge Sort.

In fact, I want to tell you that we have begun to cross a line of thinking and understanding sort algorithms. Because the advanced sort algorithms we will see, like Merge Sort and Quick Sort, all are available to involve with a new concept called Recursive Process; And sub-groups a big array to smaller groups to simpler the sort process step by step. Yes, Sub-Grouping is the key to understand these sort algorithms. And This theory makes sense in real life too. If you got a big problem, knock it down to several smaller problems first, then each small problem can be handled easier and you conquer the big problem when you finished every small ones.

Focusing on Merge Sort. The sort algorithm is called this name for a obvious reason, the data list waiting for sorting will be divided into sub-lists, and the sub list will be divided into sub-lists as well. The division process will continue until the sub list only has one element inside. Now, the merging part begin. every two sub lists will be merge together in order, which means the merged list will have smaller elements on the left and larger elements on the right. The merging process will repeat until we get a data list includes all the elements again.

As we mentioned before, we can use recursive process to control the sub-grouping. Recursive Process means a function invokes itself repeatedly. Of course, there must be a condition inside the function to tell the function to stop invoking to avoid dead loop. We can see that Merge Sort is a good scenario to apply Recursive Process. Sort function will keep dividing the list until the sub list only has one element inside. We call this kind of Merge Sort is in a Top-Down way.

Unfortunately, if the list is huge enough, Top-Down way is not a very good choice, because Recursive Process need to consume a lot of stack space. Especially for JavaScript, your web browser will not be happy if you have a big array need to sort in Top-Down way. The good news is, most of the Recursive Process can be achieved in another way, Non-Recursive Process. Glad to tell you that Merge Sort has a Bottom-Up way to implement. In this way, we handle every single element in the array first, and begin to merge every two of them, them four of them, until the whole list being remerged.

In our animation show, we are using Bottom-Up Merge Sort. The reason is simple, I cannot stop the Recursive Process in a cheap way and it is controlled by JavaScript engine of web browser. But don't worry, I will give you both the sample scripts for Bottom-Up and Top-Down.

Because it is Bottom-Up Merge Sort, I will take every element in the list as a sub list at the beginning and every sub list has its own background colour. When I merge two sub lists together, a new sub list will be generated and a new colour will fill the background of elements to present a new merged list. Enjoy!