# 歸并排序
## 示意圖
## 運作步驟
### 遞歸法（Top-down）
1. 申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并后的序列
2. 設定兩個指針，最初位置分別為兩個已經排序序列的起始位置
3. 比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置
4. 重復步驟3直到某一指針到達序列尾
5. 將另一序列剩下的所有元素直接復制到合并序列尾
### 迭代法（Bottom-up）
原理如下（假設序列共有n個元素）：
1. 將序列每相鄰兩個數字進行歸并操作，形成 `ceil(n/2)`個序列，排序后每個序列包含兩/一個元素
2. 若此時序列數不是1個則將上述序列再次歸并，形成 `ceil(n/4)`個序列，每個序列包含四/三個元素
3. 重復步驟2，直到所有元素排序完畢，即序列數為1
## 算法分析
* 最壞時間復雜度 O(nlogn)
* 最優時間復雜度 O(nlogn)
* 平均時間復雜度 O(nlogn)
## 實現
```Python
def merge_sort(list):
'''Python中的普通的歸并排序算法實現
:param list: 需要排序的數字列表
:return: 排序結果
'''
# 將left 和 right 按照大小排序
def merge(left, right):
'''merge兩個list
:param left: 列表left
:param right: 列表right
:return: merge結果
'''
result = []
while left and right:
result.append(left.pop(0) if left[0] <= right[0] else right.pop(0))
return result + left + right
if len(list) <= 1:
return list # 只有一個元素時直接返回
mid = len(list) // 2
return merge(merge_sort(list[:mid]), merge_sort(list[mid:]))
def merge_sort_fast(list):
'''Python中的更快的歸并排序算法實現
:param list: 需要排序的數字列表
:return: 排序結果
'''
left, right = [], []
while len(list) > 1:
min_one, max_one = min(list), max(list)
left.append(min_one)
right.append(max_one)
list.remove(min_one)
list.remove(max_one)
right.reverse()
return left + list + right
```
## 測試
```
$ python merge_sort.py
歸并排序>>>
請輸入需要排序的數字，用英文半角逗號隔開，直接回車則使用默認數據：
需要排序的數字為：
1,4,2,3.6,-1,0,25,-34,8,9,1,0
merge_sort結果為：
-34,-1,0,0,1,1,2,3.6,4,8,9,25
運行一萬次，merge_sort耗時： 0.2273240089416504
merge_sort_fast結果為：
-34,-1,0,0,1,1,2,3.6,4,8,9,25
運行一萬次，merge_sort_fast耗時： 0.07656192779541016
此例子中，merge_sort_fast的效率是merge_sort的倍數： 2.0
```
# 代碼庫地址
[https://github.com/liuzhen153/play-algorithm-python](https://github.com/liuzhen153/play-algorithm-python)
