# 合併排序 (Merge sort)

## 簡介
該排序法採用經典的分治策略(Divide and Conquer)將問題分(divide)成一些小的問題然後遞迴求解，而治(conquer)的階段則將分的階段得到的各答案修補在一起，即分而治之。

合併排序法為**穩定排序法**。

## 算法

假設有一陣列 [8, 4, 5, 7, 1, 3, 6, 2]，會先將陣列每次拆分成兩組同大小的子陣列，直到每組都只有一個元素再進行排序後合併。

流程如下圖：


分的部分很好實現，就是每次都拆分成兩半，合的部分需要花點時間想一下。

## 思路

分的部分應該很好理解，所以著重講一下治(conquer)的部分。

我們需要將兩個已經有序的子序列合併成一個有序序列，比如上圖中的最後一次合併，要將 [4,5,7,8] 和 [1,2,3,6] 兩個已經有序的子序列，合併為最終序列 [1,2,3,4,5,6,7,8]。

將 i 索引指向陣列第一個元素，j 索引指向 mid + 1(右子序列第一個元素)，將i 與 j 進行比較，哪個元素比較小就放到 temp 中轉陣列中存放，並且記得將索引後移，一直重複比較直到某一子序列已經遍歷結束。

來看下實現步驟：


若某一子序列已經遍歷結束但另一子序列還未遍歷結束，則會將那個子序列的剩下元素全部放進 temp 陣列中，最後將 temp 陣列 copy 回 arr 陣列。


### 詳細步驟

1. 構建 temp 陣列，定義左右為 left: 0 , right: n - 1
2. 指定邊際條件 左邊的索引要小於右邊
3. 找出中間索引 (mid)
4. 拆分左邊和右邊 (呼叫函數)
5. 左陣列和右陣列比大小，小的先放進去
6. 如果剩餘元素還沒有放完，就把剩下的元素放進temp中
7. 將 temp copy 到 nums

## 參考資料
- [合併排序詳解](https://hackmd.io/@Aquamay/H1nxBOLcO/https%3A%2F%2Fhackmd.io%2F%40Aquamay%2FHJgJ3hxkou)