Skip to content

Instantly share code, notes, and snippets.

@airspeedswift
Last active January 20, 2017 12:29
Show Gist options
  • Star 2 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save airspeedswift/dfd2c369635cee4fa779 to your computer and use it in GitHub Desktop.
Save airspeedswift/dfd2c369635cee4fa779 to your computer and use it in GitHub Desktop.
Stable Swift merge sort
extension Array where Element: Comparable
{
mutating func mergesortInPlace() {
var tmp: [Generator.Element] = []
tmp.reserveCapacity(numericCast(self.count))
func merge(lo: Int, _ mi: Int, _ hi: Int) {
tmp.removeAll(keepCapacity: true)
tmp.extend(self[lo..<hi])
var i = 0, var j = mi - lo
let imax = j, jmax = tmp.count
for k in lo..<hi {
if i == imax { self[k] = tmp[j++] }
else if j == jmax { self[k] = tmp[i++] }
else if tmp[j] < tmp[i] { self[k] = tmp[j++] }
else { self[k] = tmp[i++] }
}
}
let N = self.count
for var sz = 1 ; sz < N ; sz += sz {
for var lo = 0; lo < N-sz ; lo += sz + sz {
merge(lo, (lo+sz), min(lo+sz+sz,N))
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment