关于javascript:归并排序JS实现

归并排序（Merge Sort）是建设在归并操作上的一种无效，稳固的排序算法，该算法是采纳分治法（Divide and Conquer）的一个十分典型的利用。将已有序的子序列合并，失去齐全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

整个归并排序分成两个阶段，第一个阶段是分，将整个数组分成单个元素的子序列，因为只有一个元素的子序列必定是有序的。
第二个阶段是合并，将分成的每个子序列逐步合并成一个残缺有序的数组。

如图：

从图中能够看出，分出的二叉树深度为log2n（如数组总长度为8，则树的深度为3），而合并操作的均匀工夫复杂度为 O(n)，那么归并排序的平局工夫复杂度就是 O(nlogn)

代码实现如下：

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]