[排序演算法]Merge sort — 合併排序法

photo by @shs521

Merge Sort採用分治法(Divide and Conquer)的方式來處理排序的問題，簡單介紹一下分治法執行的步驟如下:

1. Divide:先將大問題不斷切割成小問題
2. Conquer:用遞迴的方式處理所有的子問題
3. Combine:將所有的結果合併起來就是最終解答

實作步驟:

將陣列不斷分割，分割到只有一個元素為止，再依照大小依序組合起來，流程可參考下圖

用js實作merge sort

這邊畫流程圖來講解merge這個函式在做的事情

1. 假設傳入兩個陣列個別是arr1 和arr2 (這兩個必定是已經排序好的陣列)

2. 第一個while迴圈會搭配雙指針將兩個陣列相互比大小，先取兩個陣列中的第一個來做比較，1比2小所以放入result裡面，然後本來指向1的j指針就要往後移動一格，指向4

3. 2與4做比較，2比較小所以放入result中，本來指向2的i指針就要往後移動一格，指向3

4. 經過不斷的比較會發現i指針已經指到最後一個了，但是j指針還沒到終點，此時第一個while迴圈已經終止，可以發現arr1的已經全部被放進result裡面了，arr2還有兩個

5.因此會執行第三個while迴圈，將arr2剩下的元素放進result，如果今天是arr1有剩餘的元素就會執行第二個while迴圈，最後可以得到一個合併好的陣列並且排序由小到大

空間複雜度相較其它排序演算法會比較高，因為會不斷切割生成新的陣列，需要額外的記憶體空間來存放

時間複雜度

👍在最差的情況下， 時間複雜度是O(n log n)

👎在最佳的情況下 ， 時間複雜度是O(n log n)

🤚在平均情況下，時間複雜度為 O(n log n)

參考資料: divide-and-conquer