Skip to content

Instantly share code, notes, and snippets.

@airspeedswift
Created August 16, 2018 00:50
Show Gist options
  • Save airspeedswift/da8ca6dbbeb856f71760c972e2b4c881 to your computer and use it in GitHub Desktop.
Save airspeedswift/da8ca6dbbeb856f71760c972e2b4c881 to your computer and use it in GitHub Desktop.
Unsafe stable mergesort
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: <)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment