---
# System prepended metadata

title: mergeSort
tags: [排序, mergesort]

---

# 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))
```