算法--归并排序

什么是归并排序？

归并排序就是将已有序的子序列合并成新的有序序列

思路：

有如下两个子序列：

array1 = [1, 3, 5, 10];
array2 = [2, 3, 6, 8];

有几个子序列就需要几个指针，从每个子序列的第一项开始，比如有array1[0]和array2[0]进行比较，满足条件就放入结果数组 result = []; 中，然后移动对应满足条件子序列的指针， 直到遍历完所有序列的所有元素， 然后得到最后的结果。 对于一个无序数组，先把它分成左右两段，对每段再进行相同的归并排序，递归之后得到最终结果。

JS代码：

function mergeSort(arr){
  if (arr.length < 2) {
    return arr;
  }
  var middle = parseInt(arr.length / 2);
  var left = arr.slice(0, middle);
  var right = arr.slice(middle);
  if(left=="undefined"&&right=="undefined"){
       return false;
  }
  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right){
  var result = [];
  while (left.length && right.length) {
    if(left[0] <= right[0]){
       result.push(left.shift());
    }else{
       result.push(right.shift());
    }
  }
  while (left.length){
      result.push(left.shift());
  } 
  while (right.length){
      result.push(right.shift());
  }
  return result;
}
var nums=[6,10,1,9,4,8,2,7,3,5]；
mergeSort(nums);