# mergeSort ###### tags: `排序` `mergesort` 合併排序法(Merge Sort)原理是會先將原始資料分割成兩個資料列，接著再將兩個資料繼續分割成兩個資料列，依此類推，直到無法再分割，也就是每組都只剩下一筆資料時，再兩兩合併各組資料，合併時也會進行該組排序，每次排序都是比較最左邊的資料，將較小的資料加到新的資料列中，依此類推，直到最後合併成一個排序好的資料列為止。 下面利用 ``` 30 10 40 70 50 90 60 20 ``` 由小到大排序。 ![Uploading file..._syzt76yk9]() `時間複雜度 = 分割步驟數 + 合併步驟數` 分割：分割含有 n 個資料需要 n-1 次，O(n)。合併：合併的兩邊共用 n 個元素，每次都是比較最左邊的資料，將較小的加到新陣列中，因此每次排序與合併必須經過 n 次，每回合log n次，O(log n)。 每回合意思是指每一行算一回合，因為每次都是2 的指數在成長，所以只需要logn ，但是合併同時需要sort 就需要n次 ，所以平均複雜度是nlogn # 分割的部分程式碼(幫助理解用) 遞迴就是 第一層我們原本要return 但是發現devide(right )是一個未知的東西，於是我們就想要得到一個確定的值，所以我們就執行他，去求解，然後一直這樣持續，直到最後一層，return data 終於有個確定的值了，就依造順序，往上給原本執行他要求解的層，然後又一值這樣持續，直到最上層，把我們一開始想要return 的確定的值找到了，就return 給主函式data ，並結束遞迴 ```python= data = [89, 34, 23, 78, 67, 100, 66, 29, 79, 55, 78, 88, 92, 96, 96, 23] def devide(data): if len(data)<2: return data n=len(data) mid=n//2 right=data[mid:] left=data[:mid] print("目前的總長度=",n,"//////","目前的中點位置",mid) print(left,"-----",right) return devide(left), devide(right) devide(data) ``` 輸出 ```python= 目前的長度= 16 ////// 目前的中點位置 8 [89, 34, 23, 78, 67, 100, 66, 29] ----- [79, 55, 78, 88, 92, 96, 96, 23] 目前的長度= 8 ////// 目前的中點位置 4 [89, 34, 23, 78] ----- [67, 100, 66, 29] 目前的長度= 4 ////// 目前的中點位置 2 [89, 34] ----- [23, 78] 目前的長度= 2 ////// 目前的中點位置 1 [89] ----- [34] 目前的長度= 2 ////// 目前的中點位置 1 [23] ----- [78] 目前的長度= 4 ////// 目前的中點位置 2 [67, 100] ----- [66, 29] 目前的長度= 2 ////// 目前的中點位置 1 [67] ----- [100] 目前的長度= 2 ////// 目前的中點位置 1 [66] ----- [29] 我們可以看到他都是先分右邊，分到底之後才去拿左邊來分，這和最後我們return 的順序有關 目前的長度= 8 ////// 目前的中點位置 4 [79, 55, 78, 88] ----- [92, 96, 96, 23] 目前的長度= 4 ////// 目前的中點位置 2 [79, 55] ----- [78, 88] 目前的長度= 2 ////// 目前的中點位置 1 [79] ----- [55] 目前的長度= 2 ////// 目前的中點位置 1 [78] ----- [88] 目前的長度= 4 ////// 目前的中點位置 2 [92, 96] ----- [96, 23] 目前的長度= 2 ////// 目前的中點位置 1 [92] ----- [96] 目前的長度= 2 ////// 目前的中點位置 1 [96] ----- [23] ``` 全部程式碼 ```python= data = [89, 34, 23, 78, 67, 100, 66, 29, 79, 55, 78, 88, 92, 96, 96, 23] def devide(data): if len(data)<2: return data n=len(data) mid=n//2 right=data[mid:] left=data[:mid] print("目前的總長度=",n,"//////","目前的中點位置",mid) print(left,"-----",right) return merge(devide(left), devide(right)) # 這邊因為平行一起傳入一個function 所以為logN def merge(right,left): result=[] while len(right) and len(left): if right[0]>left[0]: result.append(left.pop(0))#這邊用pop我們就不用在移動index 直接取出就好 else : result.append(right.pop(0)) result= result+right if len(right) else result+left return result print(devide(data)) ```