SOURCE

//将序列不断地进行等分，直至序列的长度为1或者2，然后由子序列向父序列方向进行同级比较
function mergeSort(arr){
  var len = arr.length;
  if (len <=1 ){
    return arr;
  }
  var middle = Math.floor( len/2 );
  var left = arr.slice(0,middle);
  var right = arr.slice(middle);
  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 arr = [6,1,2,7,9,3,4,5,10,8];
console.log(mergeSort(arr));