合併排序法原理
合併排序法屬於分治法（Divide and Conquer）演算法，先把大問題拆解成小問題，解決小問題後再將小問題合併，進而解決大問題。
圖片來源
合併排序法運作
合併排序法採用 Divide and Conquer ，其運作有兩個步驟：
- Divide：先將元素列進行遞迴對半分割。
[6, 5, 3, 1, 8, 7, 2, 4]
[6, 5, 3, 1][8, 7, 2, 4]
[6, 5][3, 1][8, 7][2, 4]
[6][5][3][1][8][7][2][4]
- Conquer：將所有小數列比較大小後合併。
[6][5] => [5, 6]
[3][1] => [1, 3]
[8][7] => [7, 8]
[2][4] => [2, 4]
[5, 6][1, 3] => [1, 3, 5, 6]
[7, 8][2, 4] => [2, 4, 7, 8]
[1, 3, 5, 6][2, 4, 7, 8] => [1, 2, 3, 4, 5, 6, 7, 8]
完成上述兩步驟，即完成合併排序法。
合併排序法時間複雜度（Time complexity）
在二分搜尋演算法 (Binary Search Algorithm)有計算時間複雜度，合併排序法內含有 Binary Search 對半分割的方法，所以時間複雜度為 log2(n)。而每個合併動作都要做兩個陣列的排序才合併，時間複雜度為 n。兩者加再一起的時間複雜度為 O(n log2(n))
Merge Sort 的時間複雜度是多少？ O(n log2(n))
合併排序法實作
按照合併排序法的第一個步驟，要先進行 Divide：
1. 使用遞迴將陣列分割到最小（6~11)。
2. 若已經是最小的就進行 merge（13）。
接著進行 Conquer：
1. 先判斷是否左右邊 index 都在陣列長度內。
2. 左邊第一個元素與右邊第一個元素比較。
3. 若左邊較大，則右邊元素放入陣列，右邊 index + 1，反之亦然。
1def mergesort(items):
2
3 if len(items) <= 1:
4 return items
5
6 mid = len(items) // 2
7 left = items[:mid]
8 right = items[mid:]
9
10 left = mergesort(left)
11 right = mergesort(right)
12
13 return merge(left, right)
14
15def merge(left, right):
16
17 merged = []
18 left_index = 0
19 right_index = 0
20
21 while left_index < len(left) and right_index < len(right):
22 if left[left_index] > right[right_index]:
23 merged.append(right[right_index])
24 right_index += 1
25 else:
26 merged.append(left[left_index])
27 left_index += 1
28
29 merged += left[left_index:]
30 merged += right[right_index:]
31
32 return merged
33
34
35test_list_1 = [8, 3, 1, 7, 0, 10, 2]
36test_list_2 = [1, 0]
37test_list_3 = [97, 98, 99]
38print('{} to {}'.format(test_list_1, mergesort(test_list_1)))
39print('{} to {}'.format(test_list_2, mergesort(test_list_2)))
40print('{} to {}'.format(test_list_3, mergesort(test_list_3)))
練習程式碼
Resource
- Comparison Sort: Merge Sort(合併排序法)
- 合併排序