Merge Sort

Algorithms ⟩ Sorting ⟩ merge sort

// 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)
    }
}

💈範例：

// 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, ...

the sorted(by:) function is actually 2 different functions.

one requires Comparable and uses < internally.
the other lets you specify the sorting logic directly (Comparable conformance not required).

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

👉 Reference default comparison function as a function parameter

⭐️ 注意：

要將 < 設為函數參數預設值時，必須使用 () 小括號，否則會產生錯誤❗️

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

👉 Reference default comparison function as a function parameter

if you need to sort huge data, you have to prepare an additional space of the same size, which is a weak point of merge sort. This is one of main reasons why it is not used as frequently as the quick sort algorithm ...

📗 參考：First Course in Algorithms Through Puzzles (2019), 3.3 Sorting

Previousranking list NextFiltering

Last updated 2 years ago