SOURCE

function mergeSort (arr) {
  if (arr.length <= 1) {
    return arr;
  }
  // 分割数组
  var mid = Math.floor(arr.length/2);
  var left = arr.slice(0, mid);
  var right = arr.slice(mid, arr.length);
  return merge(mergeSort(left), mergeSort(right));
}
function merge (left, right) {
  var leftIndex = 0;
  var rightIndex = 0;
  var arr = [];
  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] > right[rightIndex]) {
      arr.push(right[rightIndex++]);
    }
    if (left[leftIndex] < right[rightIndex]) {
      arr.push(left[leftIndex++]);
    }
  }
  // 说明有一边遍历完成
  // 另一边需要追加到数组里
  while (leftIndex < left.length) {
    arr.push(left[leftIndex++]);
  }
  while (rightIndex < right.length) {
    arr.push(right[rightIndex++]);
  }
  return arr;
}
let arr = [1, 3, 2, 5, 4]
console.log(mergeSort(arr)) // [1, 2, 3, 4, 5]