merge sort

Merge Sort In Swift

There are a lot of sorting algorithms. In this post we will take a look at implementing merge sort in Swift.

Hint: This post is using Swift 3

Swift has a build in array-sort algorithm which is very fast. Nevertheless it’s interesting to implement a sorting algorithm on your own – you can learn a lot by doing so.

The idea of merge sort

The idea of merge sort is very simple: First, the list will be divided until every item is on its own. Then, new lists will be created, beginning with lists of two items. In this step it’s very straightforward to sort these small lists. Then, we combine always two list to another sorted list of four items. This steps get’s repeated until all items are sorted in one list.

Example

Let’s take a look at an example:

We want to sort the list [98,1,45,13,6]. First, the list will be divided, the divided lists will again divided and so on. The process will be stopped, when every list has exactly one item. In the picture that is accomplished in line four. Then, always two lists will be merged. The process will be repeated until only one list is left – and this list is now sorted.

Implementing merge sort

Now let’s implement the algorithm in Swift. There are different approaches for solving that problem, we will take a recursive one:

The function  mergeSort divides the list into two list and returns the merged and sorted list by using the function  merge. Within the function call, the function calls itself recursively for both lists. When mergeSort gets a list, that has just one element, it returns the whole list.

The function  merge always compares the first items of the two lists and appends the smaller item to the new sorted list.

Testing the algorithm

Now we can test the algorithm:

Everything works as expected.

References

Title image: @ Garsya / shutterstock.com

Book Tip

Big Nerd Range Guide: iOS Programming: Excellent introduction to iOS development. Some programming experience is recommended.

Amazon