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

# ADA 2.4 Merge Sort 合併排序法


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 = 切點

---

### 時間複雜度



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

---

How to Slove Recurrence Relations?
1. Substitution Method(取代法)

2. Recursion Method(遞迴數法)

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

---

### 演算法 by raywenderlich

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
}