# Merge Sort

[Algorithms](https://lochiwei.gitbook.io/ios/algorithms) ⟩ [Sorting](https://lochiwei.gitbook.io/ios/algorithms/sort) ⟩ merge sort

{% tabs %}
{% tab title="💾 程式" %} <img src="https://1830103165-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-M5-JmwCZMKh_d7RfBaN%2Fuploads%2FuXRO6XA7Ay4wE1opokTh%2Ffile.drawing.svg?alt=media&#x26;token=8a5beff7-87fd-4527-8967-71447a762cec" alt="" class="gitbook-drawing">

```swift
// merge sort
extension Array where Element: Comparable {
    
    typealias Comparison = (Element, Element) -> Bool
    
    // ⭐️ array.split()
    // (split into 2 subarrays)
    private func split() -> ([Element], [Element]) {
        let half = count / 2
        return (Array(self[..<half]), Array(self[half...]))
    }
    
    // ⭐️ array.merge(with: other)
    // ❗️ precondition: 2 arrays must be ordered
    private func merge(with array: [Element], comparison: Comparison) -> [Element] {
        
        var result = [Element]()
        var i = 0, j = 0        // index for smallest element in each array
        
        // merge phase 1: 
        // compare smallest element from 2 arrays (both NOT empty)
        while i < self.count, j < array.count {
            
            // get smallest element in each array
            let s1 = self[i]
            let s2 = array[j]
            
            // compare 2 smallest elements
            if comparison(s1, s2) {
                result.append(s1)
                i += 1
            } else {
                result.append(s2)
                j += 1
            }
        }
        
        // merge phase 2: 
        // append rest elements (at least one of the arrays is empty)
        result += self[i...]
        result += array[j...]
        
        return result
    }
    
    // ⭐️ array.mergeSort(by:)
    //   default comparison function → ╭⭐️╮
    func mergeSort(by op: Comparison = (<) ) -> [Element] {
        
        //////////    ⭐️ base case     //////////
        
        guard count > 1 else { return self }
        
        //////////   ⭐️ recursive case    //////////
        
        // ⭐️ 1. split into 2 subarrays
        var (arr1, arr2) = self.split()
        
        // ⭐️ 2. sort subarrays (recursively)
        arr1 = arr1.mergeSort(by: op)
        arr2 = arr2.mergeSort(by: op)
        
        // ⭐️ 3. merge subarrays
        return arr1.merge(with: arr2, comparison: op)
    }
}
```

💈範例：

```swift
// test merge sort
let arr = [15, 1, 5, 8, 9, 10, 2, 50, 40, 3, 2, 9, 10, 7, 33, 34]
arr.mergeSort()             // 1, 2, 2, 3 ...
arr.mergeSort(by: >)        // 50, 40, 34, ...
```

{% endtab %}

{% tab title="🖥️ 影片" %}
{% embed url="<https://youtu.be/es2T6KY45cA>" %}
udiprod ⟩ Merge Sort vs Quick Sort
{% endembed %}
{% endtab %}

{% tab title="⭐️ 重點" %}
{% hint style="info" %}
the <mark style="color:purple;">**`sorted(by:)`**</mark> function is actually <mark style="color:red;">**2 different functions**</mark>.&#x20;

* one requires <mark style="color:purple;">**`Comparable`**</mark> and uses <mark style="color:purple;">**`<`**</mark> internally.&#x20;
* the other lets you specify the <mark style="color:red;">**sorting logic**</mark> directly (<mark style="color:purple;">**`Comparable`**</mark> conformance <mark style="color:orange;">**not required**</mark>).&#x20;

... this convenience sorting by `keyPath` would still require 2 functions.

👉 [Reference default comparison function as a function parameter](https://stackoverflow.com/a/60829002/5409815)
{% endhint %}

{% hint style="danger" %}
⭐️ 注意：

* 要將 <mark style="color:purple;">**`<`**</mark> 設為函數<mark style="color:orange;">參數預設值</mark>時，必須使用 <mark style="color:purple;">**`()`**</mark> 小括號，否則會產生錯誤❗️

```swift
//            ⭐️ default comparison ╮
func mergeSort(by op: Comparison = (<) )
```

👉 [Reference default comparison function as a function parameter](https://stackoverflow.com/a/60829002/5409815)
{% endhint %}

{% hint style="success" %}
if you need to sort <mark style="color:orange;">**huge data**</mark>, you have to prepare an <mark style="color:red;">**additional space**</mark> of the <mark style="color:orange;">**same size**</mark>, which is a **weak point** of **merge sort**. This is one of main reasons why it is **not used as frequently** as the <mark style="color:red;">**quick sort**</mark> algorithm ...

📗 參考：First Course in Algorithms Through Puzzles (2019), 3.3 Sorting
{% endhint %}
{% endtab %}

{% tab title="📗 參考" %}

* [x] First Course in Algorithms Through Puzzles (2019), 3.3 Sorting
* [x] Holy Swift ⟩ [Merge Sort: Classic Algorithm Series in Swift](https://holyswift.app/merge-sort-classic-algorithm-series-in-swift)
* [x] Ray ⟩ [Swift Algorithm Club: Swift Merge Sort](https://www.raywenderlich.com/741-swift-algorithm-club-swift-merge-sort)
* [ ] Thinkdiff ⟩ [Merge Sort — Swift](https://thinkdiff.net/merge-sort-swift-e0e77f520f89)
  {% endtab %}

{% tab title="📘 手冊" %}

* [Swift ](https://developer.apple.com/documentation/swift) ⟩ [Array ](https://developer.apple.com/documentation/swift/array)⟩ [ArraySlice](https://developer.apple.com/documentation/swift/arrayslice)
  {% endtab %}

{% tab title="🗣 討論" %}

* [Reference default comparison function as a function parameter](https://stackoverflow.com/a/60829002/5409815)
* [How to split an array in half in Swift?](https://stackoverflow.com/a/32074739/5409815)
  {% endtab %}

{% tab title="👥 相關" %}

* can sort [array](https://lochiwei.gitbook.io/ios/swift/type/category/basic/array "mention").
* [arr.split-where](https://lochiwei.gitbook.io/ios/swift/type/category/basic/array/arr.split-where "mention") splits array into subarrays by <mark style="color:orange;">**comparing consecutive elements**</mark>.
  {% endtab %}
  {% endtabs %}