归并排序算法（JavaScript实现）

归并排序是是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。

算法思想

• 把 n 个元素看成 n 个长度为 l 的有序子表
• 进行两两归并使记录关键字有序，得到 n/2 个长度为 2 的有序子表
• 重复第 2 步直到所有记录归并成一个长度为 n 的有序表为止。

举例分析

现有一数组：arr = [1,5,7,2,6,3,8,9]
当我使用归并排序的时候，首先将数组元素看成是长度为1的表，则：

[1]   [5]    [7]    [2]    [6]    [3]    [8]    [9]

那么我们先两两合并，即合并为：

[1 , 5]  [7 , 2]  [6 , 3]  [8 , 9]
   |        |        |        |    
[1 , 5]  [2 , 7]  [3 , 6]  [8 , 9]

那么我们继续进行两两表合并，即合并为：

[1 , 5 , 2 , 7]   [3 , 6 , 8 , 9]
       |                 |  
[1 , 2 , 5 , 7]   [3 , 6 , 8 , 9]

继续合并：

[1 , 2 , 5 , 7 , 3 , 6 , 8 , 9]
               |
[1 , 2 , 3 , 5 , 6 , 7 , 8 , 9]

那么我们的归并排序就完成了

代码

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

function merge(left,right){
  var result = [];
  var i = 0, j = 0;
  while(i < left.length && j < right.length){
    if(left[i] > right[j]){
      result.push(right[j++]);
    }
    else{
      result.push(left[i++]);
    }
  }
  while(i < left.length){
    result.push(left[i++]);
  }
  while(j < right.length){
    result.push(right[j++]);
  }
  
  return result;
}

var arr = [1, 2, 3, 5, 6, 7, 8, 9];
var result = merge_sort(arr);
console.log(result);  //[1, 2, 3, 5, 6, 7, 8, 9]