Sliceable mergesort extension

mergesort.swift

extension Range where T: RandomAccessIndexType {
    var mid: T {
        return startIndex.advancedBy(
            startIndex.distanceTo(endIndex) / 2
        )
    }
}

extension Sliceable
where Self: RangeReplaceableCollectionType,
      Index: RandomAccessIndexType,
      SubSlice.Generator.Element == Generator.Element
{
    mutating func merge(left: Range<Index>, _ right: Range<Index>, isOrderedBefore: (Generator.Element,Generator.Element)->Bool) {
        
        var tmp = Self()
        tmp.reserveCapacity(numericCast(left.count + right.count))
        
        var l = left.startIndex, r = right.startIndex
        while l != left.endIndex && r != right.endIndex {
            if isOrderedBefore(self[l],self[r]) {
                tmp.append(self[l++])
            }
            else {
                tmp.append(self[r++])
            }
        }
        
        tmp.extend(self[l..<left.endIndex])
        tmp.extend(self[r..<right.endIndex])
        self.replaceRange(left.startIndex..<right.endIndex, with: tmp)
        
    }
}


extension Sliceable
where Self: RangeReplaceableCollectionType,
      SubSlice.Generator.Element == Generator.Element,
      Index: RandomAccessIndexType,
      Generator.Element: Comparable
{
    private mutating func mergesortInPlace(range: Range<Index>) {
        if range.count > 1 {
            let m = range.mid
            let l = range.startIndex..<m
            let r = m..<range.endIndex
            mergesortInPlace(l)
            mergesortInPlace(r)
            merge(l, r, isOrderedBefore: <)
        }
    }
    
    mutating func mergesortInPlace() {
        mergesortInPlace(indices)
    }
    
    func mergesort() -> Self {
        var tmp = Self()
        tmp.extend(self)
        tmp.mergesortInPlace(tmp.indices)
        return tmp
    }

}


import CoreFoundation

let a = (0..<100).map { _ in arc4random() }

let start = CFAbsoluteTimeGetCurrent()
let m = a.mergesort()
let mid = CFAbsoluteTimeGetCurrent()
let s = a.sort()
let end = CFAbsoluteTimeGetCurrent()

print("mergesort: \((mid - start)*1_000)")
print("introsort: \((end - mid)*1_000)")

precondition(m == s)