MergeSort(合併排序法)

function mergeArr(arr1, arr2) {
  // arr1,arr2都是已經sorted的array
  let result = [];
  let pointer1 = 0;
  let pointer2 = 0;
  // 比較大小 選擇誰放進去result裡
  while (pointer1 < arr1.length && pointer2 < arr2.length) {
    if (arr1[pointer1] > arr2[pointer2]) {
      result.push(arr2[pointer2]);
      pointer2++;
    } else {
      result.push(arr1[pointer1]);
      pointer1++;
    }
  }
  // 剩下的那個array直接丟進result中
  while (pointer1 < arr1.length) {
    result.push(arr1[pointer1]);
    pointer1++;
  }
  while (pointer2 < arr2.length) {
    result.push(arr2[pointer2]);
    pointer2++;
  }
  return result;
}

function mergeSort(arr) {
  if (arr.length === 1) return arr;
  const middle = Math.floor(arr.length / 2);
  const left = arr.slice(0, middle);
  const right = arr.slice(middle, arr.length);
  return mergeArr(mergeSort(left), mergeSort(right));
}

console.log(mergeSort([14, -4, 17, 6, 8, -9]));