Merge Sort (JS implementation)

Merge Sort is an efficient and stable sorting algorithm based on Merge operation. This algorithm is a very typical application of Divide and Conquer. A completely ordered sequence is obtained by combining the ordered subsequences. That is, first order each subsequence, and then order between subsequence segments. If two ordered tables are merged into one, it is called two-way merge.

The whole mergesort is divided into two stages, the first stage is divided, the whole array is divided into subsequences of single elements, because subsequences of only one element must be ordered. The second stage is merging, which gradually merges each subsequence into a fully ordered array.

As shown in figure:

As can be seen from the figure, the depth of the split binary tree is log2n (if the total length of the array is 8, the depth of the tree is 3), and the average time complexity of the merge operation is O(n), so the draw time complexity of merge sort is O(nlogn).

The code is implemented as follows:

var mergeSort = function(array){
    return mergeSortRec(array);
}
var mergeSortRec = function(array){
    var length = array.length;
    if (length === 1) {
        return array;
    }
    var mid = Math.floor(length / 2),
        left = array.slice(0, mid),
        right = array.slice(mid, length);
    return merge(mergeSortRec(left), mergeSortRec(right));
}
var merge = function(left, right){
    var result = [],
        il = 0,
        ir = 0;
    while(il < left.length && ir < right.length){
        if(left[il] < right[ir]){
            result.push(left[il++]);
        }else{
            result.push(right[ir++]);
        }
    }
    while(il < left.length){
        result.push(left[il++]);
    }
    while(ir < right.length){
        result.push(right[ir++]);
    }
    return result;
}

var createNonSortedArray = function(size){
    var array = new Array();
    for (var i = size; i > 0; i--) {
        array.push( parseInt(Math.random()*100) );  
    }
    return array;
}

var arr = createNonSortedArray(10);
arr = mergeSort(arr)
console.log(arr)    //[15, 22, 25, 54, 56, 57, 66, 69, 78, 89]