归并排序，递归实现分治，将数据源递归分割成最小单位，然后递归将这些最小有序的单位合并成大的有序集合。Merge Sort, Divide and Conquer.

mergeSort.js

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

function mergeSort(arr) {
  var len = arr.length;
  if(len < 2) return arr; // 只有一个元素的数组天然有序
  var midIndex = Math.floor(len / 2);
  var leftArr = arr.slice(0, midIndex);
  var rightArr = arr.slice(midIndex);
  return merge(mergeSort(leftArr), mergeSort(rightArr));
}