归并排序

归并排序的归是递归的意思，并是将分化的半数组并在一起。

 function mergeSort(arr) {
  let length = arr.length;
  if (length < 2) return arr;
  let middle = Math.floor(length / 2);
  let left = arr.slice(0, middle);
  let right =arr.slice(middle);
  return **merge(mergeSort(left), mergeSort(right));
 }

 function **merge(left, right) {
   let 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;
}

最佳情况：T(n) = O(n)；最差情况：T(n) = O(nlogn)；平均：T(n) = O(nlogn)。