Merge sort 使用到的是 Divide and conquer 這個方法，把大問題先切割成一個個小問題，等所有小問題解決之後，大問題也解決了。有點像規劃一個旅遊行程時，你會先處理其中的小問題，比方要住哪裡，要去哪邊，用甚麼交通工具… 等你把這些小問題全部想清楚了，整個旅遊計畫也就完成了。
Merge Sort
💡 先排序小陣列，利用遞迴方式慢慢排序到整個陣列
演算法主要分成兩個步驟，分別是切割以及合併。
步驟：
- 將陣列切割到最小單位，也就是一個元素的長度
- 接著兩兩元素進行排列，並慢慢增加排序數量，直到完成排序
切割
如上圖所示，第一步是把問題縮小，先排序小陣列。因此我們把陣列不斷切割，直到最後只剩下一個元素。一個有 n 個元素的陣列，分割的次數是 n-1 次，圖中原本有 8 個元素，經過 7 次分割才完成。
分割的時間複雜度為 n-1
合併
接下來是重頭戲，把剛剛切好的元素排序完再合併回去。拿圖中由左至右四個元素來輔助說明：
(1) 第一步 [38], [27], [43], [3] 這四個小陣列兩兩進行合併，合併方式是比較最左側的元素大小，比較小的元素就放左側
(2) 因為目前小陣列都只有一個元素，沒有左右之分，直接比大小 + 合併後產生 [27, 38] 和 [3, 43] 這兩個新陣列
(3) 再來進行一次合併，記得剛剛的合併方式是比較最左側的元素誰比較小嗎？現在兩個陣列最左側的元素分別是 27 和 3，因為 3 比較小所以擺第一個，接著是 27，再來繼續進行比較，依序將 38 和 43 放到陣列
(4) 最一開始倒數的三個小陣列，也就是 [9], [82], [10] 也比照一樣的方式合併，最後會產生 [9, 10, 82]，最後再和 [3, 27, 38, 43] 做一次合併，就會產生一個排序過的陣列，此時整個排序結束
每次合併的過程中，都是將兩個小陣列各自最左側的元素拿來一一比較，如果整個陣列有 n 個元素，就會經過 n 次合併步驟。
merge sort 的合併方式是從小陣列到大陣列慢慢合併，將兩個小陣列合併的過程當作一回合的話，總共合併的回合數會是 log n
合併的時間複雜度 = 合併步驟 * 合併回合數 = n log n
遞迴
把上述的步驟寫成程式碼，你也許會好奇如何把陣列切到最小再開始合併呢？這裡會使用遞迴的方式達成。先來看一段簡單的程式碼：
程式結果最後會從 7 一路倒數印到 1 為止。程式主要邏輯是判斷 num 是否為0，如果是的話就結束，不然就印出當前數字並再一次呼叫函式本身。
像這樣子，程式碼中包含自我呼叫(self-calling)的函式我們就稱為遞迴。這邊很重要的一點是設定 base case, 也就是在什麼樣的情況下要停止自我呼叫，不然會產生無窮遞迴。以 countDown 的例子來說，我們希望倒數到 0 就停止。回到 Merge sort 來說，我們希望把陣列切割到只剩一個元素並開始合併，因此這裡的 base case 就是陣列長度為 1 的時候
程式碼：
時間複雜度：O(n log n)
將分割和合併步驟相加會得到 n-1 + n log n，常數省略不計得 n log n
空間複雜度：O(n)
每一次合併都要使用新的記憶體空間存放合併結果
