归并排序

定义

要将一个数组排序，可以先（递归）将它分成两半分别排序，然后将结果归并起来。其优势在于将任意长度为N的数组排序所需时间和NlogN成正比，劣势在于它所需要的额外空间和N成正比。

性质

对于长度为N的任意数组，自顶向下的归并排序需要1/2NlgN至NlgN次比较。

代码

使用swift实现代码如下：

class Sort {
    
    ///自顶向下归并排序
    func sort<T: Comparable>(a: inout Array<T>, lo: Int, hi: Int) {
        if lo >= hi { return }
        let mid = lo + (hi - lo) / 2
        sort(a: &a, lo: lo, hi: mid)
        sort(a: &a, lo: mid + 1, hi: hi)
        merge(a: &a, lo: lo, mid: mid, hi: hi)
    }

    ///自底向上归并排序
    func sort<T: Comparable>(a: inout Array<T>) {
        let N = a.count
        var sz = 1
        while sz < N {
            var lo = 0
            while lo < N - sz {
                merge(a: &a, lo: lo, mid: lo + sz - 1, hi: min(lo+sz+sz-1, N-1))
                lo += sz + sz
            }
            
            sz = sz + sz
        }
    }
    
    func merge<E: Comparable>( a: inout Array<E>, lo: Int, mid: Int, hi: Int) {
        
        var i = lo, j = mid + 1
        let aux = a
        
        for k in lo ... hi {
            if i > mid {
                a[k] = aux[j]
                j += 1
            } else if j > hi {
                a[k] = aux[i]
                i += 1
            } else if aux[i] < aux[j] {
                a[k] = aux[i]
                i += 1
            } else {
                a[k] = aux[j]
                j += 1
            }
        }
    }
    
}