Merge Sort Algorithm 合併排序法
2022-10-23 23:20:15
# Merge Sort 合併排序法
+ 本身就是一種 Divide and conquer **分而治之**，把陣列裁切到最小塊再組起來，merge 合併就是這個演算法實際在做的行為。
+ 兩兩陣列合併時進行排序，每個陣列都要跑一個自身長度的迴圈，去比較另一個陣列的值，依序放到新陣列中。
+ 時間複雜度為 **O(nlogn)**。
***
## 目錄
- 介紹
- BigO
- 為什麼是 O(nlogn) ?
- 參考資料
***
``` python
def merge(a1, a2):
result = []
i, j = 0, 0
# 比較 arr1[1] arr2[j] 誰比較小
while i < len(a1) and j < len(a2):
if a1[i] > a2[j]:
result.append(a2[j])
j += 1
else:
result.append(a1[i])
i += 1
# 此時已經有一格陣列跑完，將另一個剩餘加入 result
while i < len(a1):
result.append(a1[i])
i += 1
while j < len(a2):
result.append(a2[j])
j += 1
return result
def mergeSort(arr):
if len(arr) == 1: # 陣列長度為1就回傳，長度不為1，就繼續切到長度為1
return arr
else:
middle = int(len(arr)/2)
left = arr[:middle]
right = arr[middle:]
return merge(mergeSort(left), mergeSort(right))
arr = [18, 36, 5, 12, 42, 1, 99, 20]
print(mergeSort(arr))
# [1, 5, 12, 18, 20, 36, 42, 99]
```
## 介紹
函式 `merge` 在做的事如同上圖下方，兩陣列合併成一陣列並且排序好的程式碼
函式 `mergeSort` 是主要在跑的函式，其實有點像 Quick Sort 不斷分割，差別就是 Quick Sort 中個多一個 Pivot
而 Merge Sort 沒有 Pivot，單純將陣列一分為二 ( 當陣列長度大於 1 以前 )
`left = arr[:middle]` `right = arr[middle:]` 就是將陣列一分為二的程式碼
## BigO
Worst Case Performance: O(nlogn)
Best Case Performance: O(nlogn)
Average Performance: O(nlogn)
## 為什麼是 O(nlogn) ?
***
由上圖所示，本來有 8 個陣列，經過第一層合併後剩 **4** ( 8 / 2^1) 個，第二層合併剩下 **2** (8 / 2^2) 個
，第三層最後合併成 **1** ( 8 / 2^3) 個
所以如果今天有 n 個陣列，需要 (n / 2^k) 層合併後，會合併成 1 個完整陣列
因此可以依照上圖公式得出這樣的 BigO 值為 `O(nlogn)`
 
## 參考資料：
[【Day25】[演算法]-合併排序法Merge Sort - iT 邦幫忙](https://ithelp.ithome.com.tw/articles/10278179)
Udemy - 資料結構與演算法 (JavaScript)
點擊複製文章連結
X