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…

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…