Merge Sort in Swift

Merge sort is a divide and conquer algorithm that runs in O(n log n) time and was invented in 1945 by John von Neumann.

Divide and conquer algorithms breaks a problem into similar, smaller subproblems to solve the original problem.

The 3 parts of divide and conquer algorithm

After this quick introduction let’s dive into the problem and code an in-place, generic implementation of merge sort in Swift.

Define a method interface to call recursively

numbers is an array of unsorted Int s. Your target is to implement a merge sort algorithm for any array with items conform Comparable protocol.

To make in-place changes instead of returning a new array after each call array parameter is marked inout

Divide the problem into subproblems

You need to find the index midway between left most and right most indexes to divide our problem to smaller merge sort subproblems.

let middleIndex = (startIndex + endIndex) / 2

Now you can define 2 subproblems instead of 1 big problem to solve

mergeSort(array:&array, startIndex:startIndex, endIndex:middleIndex)    
mergeSort(array:&array, startIndex:middleIndex+1, endIndex:endIndex)

After solving these 2 subproblems you just need to combine solutions to have the problem solved

merge(array: &array, 
      startIndex: startIndex, 
      middleIndex: middleIndex, 
      endIndex: endIndex)

Decide what is the base case to stop recursion

Now you know how to divide the problem into subproblems but you need to decide when to stop. If you get to a point where each subarray has only 1 item in it, you don’t need and actually can’t continue creating subarrays.

2 subarrays having 1 item is our base case to solve the merge sort problem.

Combine subproblem solutions to get the solution of the initial problem

The last thing you need to implement is the merge method. Merge sort like it’s name imply is doing it’s real job in merging stage.

After creating 2 subarrays, you have 3 while loops to set items from leftSubarray or rightSubarray to the original array.

Until the exhaustion of one of the subarrays you need to compare values in left and right subarrays and set the value to the index position in array. When this comparison ends and while loop returns, you need to copy all the items of the remaining (not exhausted subarray’s) items to array.

Create a better interface for mergeSort

You finished implementing the merge sort in Swift but you can improve the function’s interface so that anyone can use the mergeSort function without needing to supply 3 arguments or thinking about inner implementation.

Download MergeSort.playground to see the full source code in action.

Happy coding.