Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Swift 3 Merge Sort
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]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.