Sorting Algorithms: Implementing Merge Sort Using SwiftJimmy M AnderssonBlockedUnblockFollowFollowingFeb 10In the previous article we looked under the hood of Heap Sort, a sorting algorithm based on a tree data structure called a Heap.
Today, we’re diving further into the world of sorting algorithms and we take a look at Merge Sort, a sorting algorithm that runs in O(n*log(n)) time, but as a trade-off requires O(n) space.
XCode Playground Files with implementations are available on this link.
What is Merge Sort?Merge Sort falls under a category of algorithms that we like to call “Divide and Conquer Algorithms”.
This builds off of the idea that it is much easier to solve a problem that involves half the data, so we try to come up with ways to recursively split our data into two somewhat equally sized data sets.
In the case of Merge Sort, it will be much easier to sort an array that is half the size of the original array.
Splitting the array into two half-size arrays will land us in a similar situation.
It will be much simpler to sort four arrays of one fourth the original size, so we perform a recursive split again.
This is the ingenious part about this algorithm.
Because we’re dealing with arrays of a finite size, we’re bound to reach a state where all arrays have less than two element, and therefore can be considered sorted.
When we reach said state, the recursion terminates and we start to unwind the call stack.
On our way back, we merge the arrays together by comparing the elements inside of each and inserting them into a new array, that will later be passed on to the next frame on the call stack.
Take a look at the following sketch to get a feel for how this works:Conceptual sketch of how the Merge Sort algorithm works.
Structuring The AlgorithmWe are going to take the protocol oriented approach on this one, meaning that we are going to extend the Array implementation for arrays containing elements that conform to the Comparable protocol.
We will also implement a method that returns a sorted copy of the array, instead of replacing the array we’re calling our method on.
These will be the implementations for those methods:extension Array where Element: Comparable { public mutating func mergeSort() { let startSlice = self[0.
<self.
count] let slice = mergeSort(startSlice) let array = Array(slice) self = array } public func mergeSorted() -> Array<Element> { let startSlice = self[0.
<self.
count] let slice = mergeSort(startSlice) let array = Array(slice) return array }}Note that we are declaring a variable called startSlice.
We are going to work with a generic structure called ArraySlice, which will help us avoid unnecessary copying of our array on our way down the call stack.
Instead, we are going to create a view into already allocated memory, and only allocate new memory when we merge two slices together.
When the call to .
mergeSort(_:) returns, we need to cast it into an Array for it to be compatible with our return type.
However, be aware that the Swift compiler is such a smart construct that it will simply let the new Array object use the already allocated memory from the ArraySlice, so there won’t be any overhead costs to talk about.
For the next part, we define our .
mergeSort(_:) method, still inside of our extension scope:private func mergeSort(_ array: ArraySlice<Element>) -> ArraySlice<Element> { if array.
count < 2 { return array } else { let midIndex = (array.
endIndex + array.
startIndex) / 2 let slice1 = mergeSort(array[array.
startIndex.
<midIndex]) let slice2 = mergeSort(array[midIndex.
<array.
endIndex]) return merge(slice1, slice2) } }This is the part where we decide whether or not the split part of our array can be considered being “sorted”.
If the piece of the array contains less than two elements, it is by definition sorted, so we just return the same array piece.
If it contains more elements, we split it again by creating two new ArraySlice objects and passing them into a recursive call.
When the two recursive calls return, we can be sure that we have two sorted array slices to work with, so we call the method merge(_:_:) to combine the two slices into one and return it.
merge(_:_:) looks like this:private func merge(_ firstArray: ArraySlice<Element>, _ secondArray: ArraySlice<Element>) -> ArraySlice<Element> { var newArray = ArraySlice<Element>() newArray.
reserveCapacity(firstArray.
count + secondArray.
count) var index1 = firstArray.
startIndex var index2 = secondArray.
startIndex while index1 < firstArray.
endIndex && index2 < secondArray.
endIndex { if firstArray[index1] < secondArray[index2] { newArray.
append(firstArray[index1]) index1 += 1 } else { newArray.
append(secondArray[index2]) index2 += 1 } } if index1 < firstArray.
endIndex { let range = index1.
<firstArray.
endIndex let remainingElements = firstArray[range] newArray.
append(contentsOf: remainingElements) } if index2 < secondArray.
endIndex { let range = index2.
<secondArray.
endIndex let remainingElements = secondArray[range] newArray.
append(contentsOf: remainingElements) } return newArray }This one is a little bit trickier, so take your time to read through and understand it.
We start off by creating a new ArraySlice object and two variables to keep track of what index we’re currently at in each of the passed in slices.
Then we compare the elements of each slice, putting the smallest element into our new ArraySlice object, until one of the original slices are done.
Finally, we check if there are any elements remaining that we need to insert.
Once that is done, we return the new slice back to the calling function and we’re finished.
That’s it for this time!.Feel free to comment if you have questions, and follow to get notifications about future articles.
To learn more about iOS Development, check out my previous articles:The Process of Designing a Custom Data StructureWhat questions do we need to ask ourselves when designing a custom data structure?medium.
comUsing Swift Property Observers To Clean Up ObjectsWhat are Swift Property Observers and how can we use them to clean up our objects for outside developers?medium.
comThis story is published in The Startup, Medium’s largest entrepreneurship publication followed by +422,678 people.
Subscribe to receive our top stories here.
.