Merge Sort with Swift

This post is a part of my new series on algorithms in Swift. I am providing these as both a tutorial to help others and as an opportunity for me to grow. Recently I have been working to try to solidify some of the gaps in my knowledge, and I know that teaching is in fact the road to mastery. Check back for more updates in the SwiftyAlgos series.

Merge Sort is a great tool for taking an array of equatable values to sorting them quickly into the correct order. The main drawback to merge sort is the potential memory footprint, however, for smaller collections its a great option. To learn more about the specifics of merge sort checkout this article on GeeksForGeeks.

First a quick discussion on how merge sort works…

Merge sort works by taking a collection and breaking it down into a series of smaller collections, then by comparing the values within those collections it systematically builds an ordered collection.

It works like this…

Here is another diagram that might help …

How to implement this in swift…

our first function splits the array in half, we use this recursively until we are no longer able to split our array
the second function takes in two arrays, and compares their first values, using a loop to update each and push values into a new ordered collection
testing the code is as easy as creating an array of random values and passing it into our mergeSort function

Check out a gist of this code on Github

After thoughts …

Merge sort is a great exercise for a number of reasons. The first is that it highlights the power of recursion in Swift, and helps to demonstrate how to implement this useful practice. Also this helps to break down some of the black magic behind how Swift standard lib and other languages sort values behind the scenes. And as always, an understanding of CS fundamentals helps us all to be better coders.

A big thanks to Sean Allen on YouTube! He has some great tutorials that have really helped me and I love his videos because they are fast and intuitive, so check him out.

Until next time…

One thought on “Merge Sort with Swift

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s