In this Swift Merge Sort tutorial, you'll learn how to implement the merge sort algorithm in a step-by-step Playground.
Great tutorial and very good explanations. Thank you!
Thanks for the concise presentation and the inclusion of generics!
let leftArray = Array(array[0…<middleIndex])
let rightArray = Array(array[middleIndex…<array.count])
Under the covers, doesn’t this create two NEW arrays – duplicating the data and the memory requirements? With a n-size array, won’t the code require log2(n) copies of the data? That would be n log2(n) ints before the merge step starts?
Update: After closer review, it’s not as bad as I first thought. But it’s still looks like a lot of duplicate data.
Yeah, you’re right. Merge sort as I know it has always been like that. It’s not a in-place sort (i.e. you need to create new containers for the array).
Thanks for a great tutorial.
Just one thought though, wouldn’t it be better to do the following:
if leftElement <= rightElement {
orderedArray.append(leftElement)
leftIndex += 1
}
if leftElement >= rightElement {
orderedArray.append(rightElement)
rightIndex += 1
}
insted of the following inside the merge function:
if leftElement < rightElement {
orderedArray.append(leftElement)
leftIndex += 1
} else if leftElement > rightElement {
orderedArray.append(rightElement)
rightIndex += 1
} else {
orderedArray.append(leftElement)
leftIndex += 1
orderedArray.append(rightElement)
rightIndex += 1
}
Short answer: I’m not sure.
I would argue though, that the bottom snippet is clearer, since it defines the 3 cases you need to take care of while merging in a discrete manner.
But yours saves a few lines of code 
I’d say either implementation is sensible.
Important to note that this isn’t a stable sort algorithm, as demonstrated by the following code:
struct Ace {
let i:Int
let s:String
}
func ==(lhs: Ace, rhs: Ace) -> Bool {
return lhs.i == rhs.i
}
func <(lhs: Ace, rhs: Ace) -> Bool {
return lhs.i < rhs.i
}
extension Ace: Comparable {}
let array = [Ace(i: 1,s: "a"),Ace(i: 1,s: "b"),Ace(i: 1,s: "c"),Ace(i: 1,s: "d"),Ace(i: 1,s: "e"),Ace(i: 1,s: "f")]
print(mergeSort(array)) // [Ace(i: 1, s: "a"), Ace(i: 1, s: "d"), Ace(i: 1, s: "b"), Ace(i: 1, s: "e"), Ace(i: 1, s: "c"), Ace(i: 1, s: "f")]
Whereas the C function mergesort is stable:
struct Ace {
let i:Int
let s:String
}
func ==(lhs: Ace, rhs: Ace) -> Bool {
return lhs.i == rhs.i
}
func <(lhs: Ace, rhs: Ace) -> Bool {
return lhs.i < rhs.i
}
extension Ace: Comparable {}
let array = [Ace(i: 1,s: "a"),Ace(i: 1,s: "b"),Ace(i: 1,s: "c"),Ace(i: 1,s: "d"),Ace(i: 1,s: "e"),Ace(i: 1,s: "f")]
mergesort(&array, array.count, MemoryLayout<Ace>.size, {
let a = $0.unsafelyUnwrapped.load(as:Ace.self)
let b = $1.unsafelyUnwrapped.load(as:Ace.self)
if a == b {
return 0
}
else if a < b {
return -1 }
else {
return 1
}
})
array // [{i 1, s "a"}, {i 1, s "b"}, {i 1, s "c"}, {i 1, s "d"}, {i 1, s "e"}, {i 1, s "f"}]
Or, Airspeed Velocity wrote a pure Swift stable sort:
// stable sort taken from AirspeedVelocity blog
// http://airspeedvelocity.net/2016/01/10/writing-a-generic-stable-sort/
extension RangeReplaceableCollection
where
Index: Strideable,
SubSequence.Iterator.Element == Iterator.Element,
IndexDistance == Index.Stride {
public mutating func stableSortInPlace(
isOrderedBefore: @escaping (Iterator.Element,Iterator.Element)->Bool
) {
let N = self.count
var aux: [Iterator.Element] = []
aux.reserveCapacity(numericCast(N))
func merge(lo: Index, mid: Index, hi: Index) {
aux.removeAll(keepingCapacity: true)
var i = lo, j = mid
while i < mid && j < hi {
if isOrderedBefore(self[j],self[i]) {
aux.append(self[j])
j = (j as! Int + 1) as! Self.Index
}
else {
aux.append(self[i])
i = (i as! Int + 1) as! Self.Index
}
}
aux.append(contentsOf:self[i..<mid])
aux.append(contentsOf:self[j..<hi])
self.replaceSubrange(lo..<hi, with: aux)
}
var sz: IndexDistance = 1
while sz < N {
for lo in stride(from:startIndex, to: endIndex-sz, by: sz*2) {
// see https://swift.org/migration-guide/
if let hiVal = self.index(lo, offsetBy:sz*2, limitedBy: endIndex) {
merge(lo:lo, mid: lo+sz, hi:hiVal)
}
}
sz *= 2
}
}
}
Hey @sketchytech, thanks for adding this. I’ve been playing with it and the results were not as expected at first. I changed one of the Ace values to be a 2 and it never put it at the end. So I made two modifications.
I got rid of the if let for the highVal and replaced it with this: let highVal = self.index(lo, offsetBy: size * 2, limitedBy: endIndex) ?? endIndex
I added a _ before the closure. _ isOrderedBefore: @escaping (Element, Element) -> Bool. That way you didn’t have to use the closure name when calling it.
The finished product was this.
extension Array {
public mutating func stableMergeSortInPlace(_ isOrderedBefore: @escaping (Element, Element) -> Bool) {
let N = self.count
var aux: [Iterator.Element] = []
aux.reserveCapacity(numericCast(N))
func merge(_ lo: Int, _ mid: Int, _ hi: Int) {
aux.removeAll(keepingCapacity: true)
var i = lo
var j = mid
while i < mid && j < hi {
if isOrderedBefore(self[j], self[i]) {
aux.append(self[j])
j += 1
} else {
aux.append(self[i])
i += 1
}
}
print(aux)
aux.append(contentsOf: self[i..<mid])
aux.append(contentsOf: self[j..<hi])
self.replaceSubrange(lo..<hi, with: aux)
}
var size: IndexDistance = 1
while size < N {
for lo in stride(from: startIndex, to: endIndex - size, by: size * 2) {
let hi = self.index(lo, offsetBy: size * 2, limitedBy: endIndex) ?? endIndex
merge(lo, lo + size, hi)
}
size *= 2
}
}
}
This tutorial is more than six months old so questions are no longer supported at the moment for it. We will update it as soon as possible. Thank you! :]