Swift 3 Merge Sort

mergesort.swift

extension RangeReplaceableCollection
  where
  // Index: RandomAccessIndexType → Self: RandomAccessCollection
  Self: RandomAccessCollection,
  // still need this, until generics allow constraints to guarantee
  // this is the case for all collections...
  SubSequence.Iterator.Element == Iterator.Element {
    // mutating in-place operations should be imperative verb phrases,
    // so let's rename this stablySort
    public mutating func stablySort (
        isOrderedBefore: (Iterator.Element,Iterator.Element)->Bool
    ) {
        let N = self.count
        
        // Generator → Iterator
        var aux: [Iterator.Element] = []
        aux.reserveCapacity(numericCast(N))
        
        func merge(_ lo: Index, _ mid: Index, _ hi: Index) {
            
            // keepCapacity: → keepingCapacity:
            aux.removeAll(keepingCapacity: true)
            
            var i = lo, j = mid
            while i < mid && j < hi {
                if isOrderedBefore(self[j],self[i]) {
                    aux.append(self[j])
                    // now need to advance indices using their collection. 
                    // "formIndex(after:)" is the in-place version (i.e. j++)
                    formIndex(after: &j)
                }
                else {
                    aux.append(self[i])
                    formIndex(after: &i)
                }
            }
            // appendContentsOf → append(contentsOf:)
            aux.append(contentsOf: self[i..<mid])
            aux.append(contentsOf: self[j..<hi])
            
            // replaceRange → replaceSubrange
            self.replaceSubrange(lo..<hi, with: aux)
        }
        
        // stride over the collection, doubling the stride each time, hence O(n log n)
        // fancy new sequence(first:next:) 😀 can replace c-style for ;; here...
        for sz in sequence(first: 1, next: { i -> IndexDistance in i * 2}) {
            // at some point this guard can become .prefix(where:)
            guard sz < N else { break }
            let upper = index(endIndex,offsetBy: -sz)
            // now that index(_:offsetBy:limitedBy:) returns an optional, this sequence
            // will stop naturally when lo hits this upper bound...
            for lo in sequence(first: startIndex, next: { self.index($0, offsetBy: sz*2, limitedBy: upper) }) {
                let mi = index(lo, offsetBy: sz)
                let hi = index(mi, offsetBy: sz, limitedBy: endIndex) ?? endIndex
                merge(lo, mi, hi)
            }
        }
    }
}

var pairs = [
    (2,1), (2,2),
    (3,1), (3,2),
    (1,1), (1,2),
    (1,3),(2,3),(3,3)
]

pairs.stablySort { $0.0 < $1.0 }
print(pairs.map { $0.1 })
// if sort is stable, ought to print
// [1, 2, 3, 1, 2, 3, 1, 2, 3]