Group Group Group Group Group Group Group Group Group

raywenderlich.com Forums

Swift Algorithm Club: Swift Merge Sort

In this Swift Merge Sort tutorial, you'll learn how to implement the merge sort algorithm in a step-by-step Playground.


This is a companion discussion topic for the original entry at https://www.raywenderlich.com/741-swift-algorithm-club-swift-merge-sort

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 :slight_smile:

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.

  1. 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

  2. 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
     }
   }
}
1 Like

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! :]