mergesort

mergesort.swift

import Darwin

func mid<T: RandomAccessIndexType>(r: Range<T>)->T {
    return r.startIndex.advancedBy(
        r.startIndex.distanceTo(r.endIndex) / 2
    )
}

func merge<T: Comparable>(inout source: [T], lhs: Range<Int>, rhs: Range<Int>) {
    var tmp: [T] = []
    tmp.reserveCapacity(count(lhs)+count(rhs))
    
    var l = lhs.startIndex, r = rhs.startIndex
    while l != lhs.endIndex && r != rhs.endIndex {
        if source[l] < source[r] {
            tmp.append(source[l++])
        }
        else {
            tmp.append(source[r++])
        }
    }
    tmp.extend(source[l..<lhs.endIndex])
    tmp.extend(source[r..<rhs.endIndex])
    source.replaceRange(lhs.startIndex..<rhs.endIndex, with: tmp)
}


func mergesort<T: Comparable>(inout source: [T], range: Range<Int>) {
    if count(range) > 1 {
        let m = mid(range)
        let l = range.startIndex..<m
        let r = m..<range.endIndex
        mergesort(&source, l)
        mergesort(&source, r)
        merge(&source, l, r)
    }
}

func mergesorted<T: Comparable>(var source: [T]) -> [T] {
    mergesort(&source, indices(source))
    return source
}

let unsorted = (1...100).map{_ in arc4random_uniform(100) }
mergesorted(unsorted)