Swift: Merge Sort with a Functional Approach

Merge sort — Google link can be found here

Merge Sort

First off let’s go over what Merge Sort is. Merge sort is the a sorting algorithm where we have an array and we break that array down until we have single elements, then we put those elements back together in the correct order. For example, say we have a list of numbers [2,1,6,3] in merge sort we break the array into two halves. That would leave us with [2,1], [6,3]. Since both of the sub arrays have more than 1 element in them we break them down again. So then we have [2],[1],[6],[3], now we can start to merge them together. We will take the first pair and compare them. For this example we will say we want to go in ascending order. Since 1 is smaller than 2 we will have [1,2] and since 3 is smaller than 6 we will have [3,6]. Now we will compare the first elements in each array and merge the two arrays. First we compare 1 and 3 that leaves us with [1] for our final sorted array. And, [2] and [3,6] for our two subarrays. We will then compare 2 and 3 since they are at index zero. 2 is smaller so we have [1,2] and then an array of [3,6] left but since we know we already sorted [3,6] we can just add that to the current list. Here is a picture to better represent it.

Now let’s get into the fun stuff.

Functional Approach

Traditionally Merge sort uses recursion to break down the array until it is a little array’s of single elements. Again since this is swift we will use an extension and a protocol to all for easy use case at the call site. Even though we will never call this just .sort(), in the real world. In order to break down the array to subarrays we will find the mid point of the remaining array. Then, we will take that remaining array from [0..<midpoint] and [midpoint..<count]. We will continue to call this until there are no array’s that have more than 1 element in them. That will look like this.

You notice we also call the combine method here. That method will take the two arrays, left & right, and combine them together in the appropriate order. If one of the arrays is empty it will return the other array. But if both arrays have elements it will compare the elements at index zero. After that the array will combine what we already have sorted and the element at index zero and recall itself. But, on this call instead of calling itself with the same left and right arguments it will take one from the array that was lower or greater depending what we are looking for. That should look like this.

So all together we have this.

A couple little things just to wrap up. You might be wondering what the double minus signs, next to left and right in the combine function, mean. Those are custom prefix operators I declared outside of the extension. Prefix operators are when you put custom symbols in front of a type and it does something to that type. There are also Postfix operators in Swift. They are the same but the go after the type. Here are some examples of them.

One last thing. The order parameter that I am always passing around. That is a higher order function.

Higher order functions

Higher order functions are when we pass a function as a parameter to anther function. This function that I am always passing around takes two Elements and returns a Bool. What it is doing is if first element is greater than or less than (depends on what I pass as a parameter) return true or false. Then based on that response handle accordingly.

Next up Quick Sort.