---
# System prepended metadata

title: ADA 2.4 Merge Sort 合併排序法
tags: [Merge Sort, ADA 2.4]

---

###### tags: `ADA 2.4` `Merge Sort`

# ADA 2.4 Merge Sort 合併排序法




![](https://i.imgur.com/Fvo3Ciy.png)

1. 先將陣列拆成兩個陣列 (可能會有一邊會是奇數)
2. 逐步將兩個陣列再拆成單一的值(n=1)
3. 針對n進行排序後，再逐步sort成有順序的陣列。


---

## Divide-and-Conquer
Base case(n=1) [1] or [99]
    ・ Directly output the liest ([1] or [99])
    
Recursive case(n>1) [6, 1, 56 ,10, 8, 101]

    ・Divide the list in to sub-lists 
    ・[6,1,56 & [10,8,101]
    
    ・Sort each sub-list recursively
    ・[1,6,56] & [8,10,101]
    
    ・Merge the two sorted lists
    ・[1,6,8,10,56,101]
    
    

---

## Pseudocode for Merge Sort
MergeSort(A, p ,r)
     //base case 判斷是否為 n = 1
     if p == r
       return
    //recursive case n > 1
    //divide to base case
    q = [(p+r-1)/2]
    //conquer
    MergeSore(A, p, q)
    MergeSore(A, q+1, r)
    //combine
    Merge(A, p, q ,r)
    
    p = 左邊邊界
    r = 右邊邊界
    q = 切點


---

### 時間複雜度
![](https://i.imgur.com/e6b8Pka.png)


![](https://i.imgur.com/V7AnbyS.png)

![](https://i.imgur.com/xrRGJCN.png)

簡記：
將n/2k展開到base case (n = 1)後再進行後續運算




---

How to Slove Recurrence Relations?
1. Substitution Method(取代法) 
![](https://i.imgur.com/3pJxwd4.png)



2. Recursion Method(遞迴數法)
![](https://i.imgur.com/AoeVwSq.png)


3. Master Method(套公式大法/大師法)

---


### 演算法 by raywenderlich
```swift=
func mergeSort<T: Comparable>(_ array: [T]) -> [T] {
    print("original:\(array)")
    //判斷n如果=1直接回傳
    guard array.count > 1 else {
        print("array \(array)")
        return array }
    
    //若>1先取得陣列總數的一半
    let middleIndex = array.count / 2
    
    //分成左右兩個Array並再次執行mergeSort，進而達成遞迴
    let leftArray = mergeSort(Array(array[0..<middleIndex]))
    print("left\(leftArray)")
    let rightArray = mergeSort(Array(array[middleIndex..<array.count]))
    print("right\(rightArray)\n")
    
    return merge(leftArray, rightArray)
    
}

func merge<T: Comparable>(_ left: [T], _ right: [T]) -> [T] {
    //已經sort完成所以開始將左右Array合併
    
    //設定左右的Index累積加入的次數
    var leftIndex = 0
    var rightIndex = 0
    
    //空Array儲存merge好的陣列
    var orderedArray: [T] = []
    
    //如果陣列的總數大於index表示還沒比較完
    //先透過index取得array相對應的值進行比較
    //小的先加入orderedArray後將index+1
    //若相同則一起加入後左右index一起+1
    while leftIndex < left.count && rightIndex < right.count {
        let leftElement = left[leftIndex]
        let rightElement = right[rightIndex]
        
        if leftElement < rightElement {
            orderedArray.append(leftElement)
            leftIndex += 1
        } else if leftElement > rightElement {
            orderedArray.append(rightElement)
            rightIndex += 1
        } else {
            orderedArray.append(leftElement)
            leftIndex += 1
            orderedArray.append(rightElement)
            rightIndex += 1
        }
    }
    
    //若左右任一邊的index = 任一邊array的總數，表示該array內的值已經全部加入到orderedArray內
    //接續將另一邊的array剩餘的值(因都已經sort好)加入到orderedArray內
    while leftIndex < left.count {
        orderedArray.append(left[leftIndex])
        leftIndex += 1
    }
    
    while rightIndex < right.count {
        orderedArray.append(right[rightIndex])
        rightIndex += 1
    }
    
    return orderedArray
}
```









