Day 28：合并排序法 Merge Sort

Merge Sort采用Divide and Conquer的方式，其实他的概念本身就是递回（recursion）。

Divide and Conquer的作法一般分成三个步骤：

1. Divide ：把问题先拆解成子问题
2. Conquer：利用递回逐一处理子问题，当子问题够小时则可以直接解（利用初始条件）
3. Combine：将子问题的结果合并

而今天会用两种方式来实作合并排序

	  index    0,1,2,3,4,5
Input: nums = [5,1,1,2,0,0]

我们一样用这个范例来举例
首先我们要把这个阵列不断的拆分成两半
像下面这样

我们先看左边
[5, 1, 1, 2, 0, 0]
[5, 1, 1][2, 0, 0]
[5][1, 1]
[5][1][1]

当我们遇到拆完两个subArray的长度恰为１的时候，我们就比较他们大小并重新建立新的已经排序好的subArray直到长度和原本的input array相同

左半边有长度1的子阵列
我们开始对他们排序
[5][1][1] -> 长度１很好比大小
接着因为我们知道两子阵列都已经排序过了，可以利用两个指标的方式来对他们合并
[1,5][1] -> 因为 1 <=1 ,把L指的数家到新的subArray[1]
 ^    ^
 |    |
 L    R
---------
[1,5][1] -> 因为 5 > 1 ,把R指的数家到新的subArray[1,1]
   ^  ^
   |  |
   L  R

----------
最後得到
[1,1,5]

利用上面的方式我们继续处理右半边

[5, 1, 1, 2, 0, 0]
[5, 1, 1][2, 0, 0]
[5][1, 1][2] [0,0]
[5][1][1][2][0][0]
-----------------
[1,1,5] [0,0,2]
一样用指标来做最後合并
[0,0,1,1,2,5]

先来看时间复杂度，过程中可以发现我们第一次复制并产生新的两个subArray且到最後仍要合并他们都会需要O(N)。
可以观察到每一层的subArray都会是上一层的一半，而且每一层的时间复杂度为O(N)，所以我们应该要思考，应该是几层(level)？
来稍微算一下，Ｎ(array的长度)＝ ２^level ⇒ level = logN
所以说，整体的时间约为O(NlogN)，而这种方式不是in place sort，空间复杂度为O(NlogN)

function mergeSort(array) {
  if (array.length <= 1) return array;
  const midInx = Math.floor(array.length / 2);
  const leftHalf = array.slice(0, midInx);
  const rightHalf = array.slice(midInx);
  return merge(mergeSort(leftHalf), mergeSort(rightHalf));
}

function merge(leftHalf, rightHalf) {
  const sortedArr = new Array(leftHalf.length + rightHalf.length);
  // k 指向 sortedArr
  let k = 0;
  // i 指向 左半
  let i = 0;
  // j 指向 右半
  let j = 0;
  while (i < leftHalf.length && j < rightHalf.length) {
    if (leftHalf[i] <= rightHalf[j]) {
      sortedArr[k++] = leftHalf[i++];
    } else {
      sortedArr[k++] = rightHalf[j++];
    }
  }
  // 做完後如果左半或右半还有剩元素 要继续放入sortedArr
  while (i < leftHalf.length) {
    sortedArr[k++] = leftHalf[i++];
  }
  while (j < rightHalf.length) {
    sortedArr[k++] = rightHalf[j++];
  }
  return sortedArr;
}

接下来我们要来思考怎麽改善空间复杂度，利用in place的方式，并且达到时间复杂度也是Ｏ(NlogN)。
我们先限制自己只能用一个input array的拷贝，这里我们拿拷贝来当主要操作的阵列。建立一个helper function来把他们当作参数来操作。

流程如下

inputArr = [5, 1, 1, 2, 0, 0] -
                               ｜呼叫helper function
copyArr =  [5, 1, 1, 2, 0, 0] -

  inputArr [5, 1, 1]-
                     ｜呼叫helper function
  copyArr  [5, 1, 1]-

  inputArr [5,1][1]-
                     ｜呼叫helper function
   copyArr [5,1][1]-

  inputArr [5][1]-
                  ｜呼叫helper（但会直接return），而後再一个个执行合并(merge)的方法
  copyArr  [5][1]-

直到最後阵列长度为1的时候，我们要把阵列做合并的动作(mergeArr)
我们要把他合并成长度为二且排列後的阵列
假设目前的左半边合并是

inputArr = [5, 1, 1, 2, 0, 0] 
copyArr =  [5, 1, 1, 2, 0, 0] 

inputArr [5, 1, 1]
copyArr  [5, 1, 1]
inputArr [5,1][1]
copyArr  [5,1][1]

----------------
inputArr [5,1]                  
copyArr  [5,1]
          ^ ^
          L R
我们用LR指标比大小 然後因为1(R)< 5(L)
我们就直接把inputArr[0]改成1,inputArr[1]改成5
也就是说我们会直接改inputArr [1,5,1,2,0,0]  
以小的部分来看，原本的
inputArr [5,1,1]
copyArr  [5,1,1]
会变成
inputArr [1,1,5]
copyArr  [5,1,1]
全部
inputArr [1,1,5,2,0,0] 
这就是原地置换(In-Place)的方式

那为什麽我们需要一个拷贝来当作辅助？

inputArr [5,1]                  
copyArr  [5,1]
          ^ ^
          L R
以这个例子来说我们在更改的时候因为把1(R)要变更inputArr[0]，也就是5要变1
如果我们没有拷贝
inputArr现在会长[1,1]  
这样5就完全消失了

function mergeSort(array) {
  if (array.length <= 1) return array;
  const copyArr = array.slice();
  helper(array, 0, array.length - 1, copyArr);
  return array;
}

function helper(inputArray, startIdx, endIdx, copyArr) {
  if (startIdx === endIdx) return;
  const midIdx = Math.floor((startIdx + endIdx) / 2);
  helper(copyArr, startIdx, midIdx, inputArray);
  helper(copyArr, midIdx + 1, endIdx, inputArray);
  merge(inputArray, startIdx, midIdx, endIdx, copyArr);
}
function merge(inputArray, startIdx, midIdx, endIdx, copyArr) {
  let k = startIdx;
  let i = startIdx;
  let j = midIdx + 1;
  while (i <= midIdx && j <= endIdx) {
    if (copyArr[i] <= copyArr[j]) {
      inputArray[k++] = copyArr[i++];
    } else {
      inputArray[k++] = copyArr[j++];
    }
  }

  while (i <= midIdx) {
    inputArray[k++] = copyArr[i++];
  }
  while (j <= endIdx) {
    inputArray[k++] = copyArr[j++];
  }
}

明天是排序的最後一次拉！

明日实作：堆积排序法(Heap Sort)