Hallo vrienden, alles goed? Leo hier. Today we will study a classic sorting algorithm called Merge Sort and how you can do it in Swift.
Today we will study what is in my opinion one of the most classic sorting algorithms, the legendary merge sort. I remember learning this in college and I was amazed by it. Thinking that you could sort something using recursion and divide-and-conquer strategies blew my mind at the time.
I can remember the young Leo sitting in the college seat when the professor of Algorithms 2 came and said: “Until this day you only study Bubble sort as a sorting strategy. Today that will change, we will learn different strategies to sort, the first one is merge sort”.
I felt like I was in an anime and I had a great challenge to surpass. And I was right. Understanding this took me way more time than anything else I had done in the coding area. To be honest, until today I think this algorithm is brilliant and I want to praise it with a blog article. Thanks, college professor, and thanks John von Neumann for creating the merge sort.
No more talking, let’s code! But first…
Painting of The Day
The artwork I chose is a 1911 painting called Violet and Gold by Frederick McCubbin. Frederick McCubbin (25 February 1855 – 20 December 1917) was an Australian artist and prominent member of the Heidelberg School art movement, also known as Australian Impressionism.
McCubbin rose to prominence for his depictions of pioneer life that captured the aspirations and the hardships of living in the Australian bush. Paintings such as Down on his luck (1889), On the Wallaby Track (1896), and The pioneer (1904) are considered images of national significance and masterpieces of Australian art.
I chose this painting because there are 4 four animals drinking water so we could order them by the colors(RGB value-based) using merge sort, right?
The Problem – Merge Sort in Swift
You have an unsorted array and want to sort its elements in a constant n*logn time.
This algorithm was created in 1945. Yes, it is that old. Check the link if you want a formal and better definition than I could give to you.
Briefly, the merge is a technique that splits the array each time until you have small enough chunks that you can do a simple comparison between the two.
Still a brilliant way to sort things. First, let’s discuss time and space complexities.
Time and Space Complexity
The time complexity is n*logn. I will not dive into what this means (search for Big O notation) but rather I will make an example.
The time complexity is O(n*logN) because let’s imagine an 8-number array.
First, we need to split it into subarrays of length 1. To do that we need to split the 8-number array 3 times. This is the logN part. For any number of inputs will be always a logN operations to split into subarrays of length 1.
But why is O(n*logn)? Because now we split the array into smaller arrays, we need to compare all numbers in all subarrays. That means for each logn we will have N comparisons. That’s why merge sort is n*logn time complexity.
The space complexity is O(n) because we will need to create at most N subarrays with length 1 to compare to each other. Something important to mention is that a lot of advancements were made from the time the merge was created and nowadays the most advanced merge sort variations are not O(n), but something like O(n*(logn)^2). We will not explore those here.
Swift Merge Sort Example
Let’s code now:
func customMergeSort(array: [Int]) -> [Int] {
guard array.count > 1 else { return array } // Mark 1
let middlePointer = array.count/2 // Mark 2
let left = customMergeSort(array: Array(array[0..<middlePointer])) // Mark 3
let right = customMergeSort(array: Array(array[middlePointer..<array.count])) // Mark 3
return mergeArrays(left,right) // Mark 4
}
func mergeArrays(_ left: [Int],_ right: [Int]) -> [Int] {
var leftIndex = 0
var rightIndex = 0
var result = [Int]()
while leftIndex < left.count && rightIndex < right.count {
if left[leftIndex] < right[rightIndex] {
result.append(left[leftIndex])
leftIndex += 1
} else if left[leftIndex] > right[rightIndex] {
result.append(right[rightIndex])
rightIndex += 1
} else {
result.append(left[leftIndex])
result.append(right[rightIndex])
leftIndex += 1
rightIndex += 1
}
}
while leftIndex < left.count {
result.append(left[leftIndex])
leftIndex += 1
}
while rightIndex < right.count {
result.append(right[rightIndex])
rightIndex += 1
}
return result
}Let’s split our explanation in two ( got the joke? ), the customMergeSort and the *mergeArrays function.
For the customMergeSort:
- This is the end of the recursion. Every time you do a recursion the first thing to think about is the end of it. If your array has length 1, just return it.
- Calculate the middle point to split the current array into two parts.
- Now start the recursion until the right and left side arrays will be left with arrays of lengths 1 or 0.
- Now we have two very small arrays we just need to merge them and going back with the recursion will make the work for us, because it will sort all the left side subarrays, all the right side subarrays, and finally merge the first and second splits.
Now the mergeArrays function is a classic merging two array strategy. You have two pointers, one for each array in the first index. Which index is smaller we put in the result array, then we increment the smaller index by 1 and repeat this operation until our arrays are empty.
To test you just need to call:
let testMikeAndPepijnArray = [1,11,12323,2,5,666,7,33,55,777,888,2,4] print(customMergeSort(array: testMikeAndPepijnArray))
Should print [1, 2, 2, 4, 5, 7, 11, 33, 55, 666, 777, 888, 12323].
And that’s it!
Continue Studying Algorithms
Studying the classics is something that is always net positive, either to refresh your memory on battle-tested concepts or to learn something really fundamental that can change the way you approach problems. Either way, one of the classic problems is dealing with palindromes and Strings, and you can study that reading this article about a special palindrome problem in Swift.
Going a step further in data structures you will find a very useful called Trie. Trie is mostly used when you have various returns for the same input and they are built one upon the other. For example, a great data structure to back an auto-correct feature is a Trie because you can use its vertices to predict and suggest words for the user. Read this article to understand how to implement the Trie data structure in Swift.
Summary – Merge Sort a Classic Algorithm Series in Swift
I hope you guys liked the content and also learned that this algorithm is like 77 years old! I didn’t know that. Interesting, right? I tend to think that everything in computer science is new and shiny, but actually, the basic structures are very old. Divide and conquer algorithms are very useful today and my advice is that you should keep learning them to keep your mind open to new approaches.
That’s all my people, I hope you liked reading this article as much as I enjoyed writing it. If you want to support this blog you can Buy Me a Coffee or leave a comment saying hello. You can also sponsor posts and I’m open to freelance writing! You can reach me on LinkedIn or Twitter and send me an e-mail through the contact page.
Thanks for reading and… That’s all folks.
Credits:
