Unsafe stable mergesort

usort.swift

extension UnsafeMutableBufferPointer {
  public mutating func merge(
    using aux: UnsafeMutableBufferPointer<Element>,
    _ lo: Int, _ mid: Int, _ hi: Int,
    by isOrderedBefore: (Element, Element) -> Bool
  ) {
    assert(hi <= self.endIndex)
    assert(self.count == aux.count)
    let from = self.baseAddress!, to = aux.baseAddress!
    var i = lo, j = mid, k = lo
    while i < mid && j < hi {
      if isOrderedBefore(from[j],from[i]) {
        (to+k).moveInitialize(from: (from+j), count: 1)
        j += 1
      } else {
        (to+k).moveInitialize(from: (from+i), count: 1)
        i += 1
      }
      k += 1
    }
    (to+k).moveInitialize(from: (from+j), count: hi-j)
    (to+k).moveInitialize(from: (from+i), count: mid-i)
    (from+lo).moveInitialize(from: to+lo, count: hi-lo)
  }
  
  public mutating func usort(
    by isOrderedBefore: (Element, Element) -> Bool
  ) {
    let N = self.count
    let aux = UnsafeMutableBufferPointer<Element>.allocate(capacity: N)

    var sz = 1
    while sz < N {
      var lo = startIndex
      let stop = index(endIndex, offsetBy: -sz)
      while lo < stop {
        let mid = index(lo, offsetBy: sz)
        let hi = index(lo, offsetBy: sz&*2, limitedBy: endIndex) ?? endIndex
        merge(using: aux, lo, mid, hi, by: isOrderedBefore)
        formIndex(&lo, offsetBy: sz&*2)
      }
      sz &*= 2
    }
  }
}

extension Array {
  public mutating func usort(by isOrderedBefore: (Element, Element)->Bool) {
    withUnsafeMutableBufferPointer { $0.usort(by: isOrderedBefore) }
  }
}


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

pairs.usort { $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]


let r = 0..<100
var a = r.map { _ in Int.random(in: r) }
a.usort(by: <)
print(a)
precondition(a == a.sorted())

var empty: [Int] = []
empty.usort(by: <)