Swift Algorithm Club: Swift Merge Sort

Kelvin Lau

SwiftAlgClub-MergeSort-feature

The Swift Algorithm Club is an open source project to implement popular algorithms and data structures in Swift.

Every month, the SAC team will feature a cool data structure or algorithm from the club in a tutorial on this site. If your want to learn more about algorithms and data structures, follow along with us!

In this tutorial, you’ll walk through one of the classics of sorting algorithms, the merge sort.

This algorithm was first implemented by Kelvin Lau, and is now refactored for tutorial format.

Note: New to the Swift Algorithm Club? Check out our getting started post first.

Getting Started

Invented in 1945 by John von Neumann, merge sort is a efficient sorting algorithm. The idea behind merge sort is to divide and conquer; To break up a big problem into small problems. A helpful mantra to remember merge sort by is split first and merge after.

Assume you’re given a pile of playing cards.

cards-01

The merge sort algorithm works as follows:

  1. Split in half. You now have two unsorted piles.cards-02
  2. Keep splitting the resulting piles until you can’t split anymore. In the end, you will have 1 card for each pile.

    cards-03
    cards-04

  3. Merge the piles together. During each merge, you put the contents in sorted order. This is easy because each individual pile is already sorted.
    cards-05cards-06cards-07

Swift Merge Sort

Let’s see what the merge sort algorithm looks like in Swift.

Open up a new Swift Playground add the following code:

let array = [7, 2, 6, 3, 9]

func mergeSort(_ array: [Int]) -> [Int] {
  
}

Here you start off with an unsorted array of integers. Your goal is to implement this function that takes an integer array and returns a new array in sorted order.

1) Split

Remember your first step is to split the array in half. To do this, update the mergeSort function to the following:

func mergeSort(_ array: [Int]) -> [Int] {
  // 1
  let middleIndex = array.count / 2
  // 2
  let leftArray = Array(array[0..

The code shouldn't compile yet, but don't worry. Your first task is to split the array in two halves.

  1. You find the middle index of the array by taking the count of the array and dividing it by half.
  2. Now that you have the middle index, you create two new arrays. The left array contains the first half of the original array, and the right array contains the second half.

2) Keep Splitting

Now that you know how to split the array in half, it's time for the second step: to keep splitting the array until you can't split anymore (i.e. each subdivision contains 1 element). That's a standard use case for recursion.

You will do this using recursion. To do this, update the mergeSort function to the following:

func mergeSort(_ array: [Int]) -> [Int] {
  // 1
  guard array.count > 1 else { return array }

  let middleIndex = array.count / 2

  // 2
  let leftArray = mergeSort(Array(array[0..

You've made 2 changes here:

  1. All recursive implementations need a base case. You can also think of it as an "exit condition". In your case, you want to stop the recursion when the array only has 1 element.
  2. You're now calling mergeSort on the left and right halves of the original array. As soon as you've split the array in half, you're going to try to split again.
Note: Understanding recursion can be quite tricky. If you're confused at how this works, try to trace out each step on paper using the test array of [7, 2, 6, 3, 9].

There's still more work to do before your code will compile. Now that you've accomplished the splitting part, it's time to focus on merging.

3) Merge

Your final step is to merge the leftArray and rightArray together. To keep things clean, you will create a separate merge function for this.

The sole responsibility of the merging function is to take in 2 sorted arrays and combine them together. The output needs to retain the sorted order. Add the following to the playground:

func merge(_ left: [Int], _ right: [Int]) -> [Int] {
  // 1
  var leftIndex = 0
  var rightIndex = 0

  // 2
  var orderedArray: [Int] = []

  // merging logic goes here!

  return orderedArray
}

This is the basic skeleton for the merging function:

  1. You've declared 2 variables - leftIndex and rightIndex. You'll use them to keep track of your progress as you parse through the two arrays.
  2. The orderedArray will house the combined array.
Quick quiz:
What's the downside of doing the following?

 
func merge(_ left: [Int], _ right: [Int]) -> [Int] {
  let combinedArray = left + right
  return combinedArray.sorted(<)
}

Solution Inside SelectShow

The strategy is to append elements from the left and right arrays one by one. Comparisons will be made at each step, ensuring that the smaller of the two elements goes into the orderedArray. Update the merge function to the following:

func merge(_ left: [Int], _ right: [Int]) -> [Int] {
  var leftIndex = 0
  var rightIndex = 0

  var orderedArray: [Int] = []
  
  // 1
  while leftIndex < left.count && rightIndex < right.count {
    // challenge!
  }

  // 2
  while leftIndex < left.count {
    orderedArray.append(left[leftIndex])
    leftIndex += 1
  }

  while rightIndex < right.count {
    orderedArray.append(right[rightIndex])
    rightIndex += 1
  }
  
  return orderedArray
}

This sets up the things to consider when iterating through the arrays:

  1. The idea is to start in the beginning, comparing the elements in left and right arrays sequentially. If you reached the end of either array, there's nothing else to compare.
  2. The first loop guarantees that either left or right is empty. Since both arrays are sorted, this ascertains that the rest of the contents in the leftover array are equal or greater than the ones currently in orderedArray. In this scenario, you'll append the rest of the elements without comparison.

Challenge

The challenge for this article is for you to implement the comparison logic. The key thing to remember is that both left and right is already sorted. Use leftIndex and rightIndex to keep track of the progress you've made on the respective arrays.

Your merging solution should be O(n) in terms of time complexity.

Solution Inside SelectShow

With that, your merging function is complete. Time to finally fix that compiler error!

Finishing up

Update the mergeSort function to the following:

func mergeSort(_ array: [Int]) -> [Int] {
  guard array.count > 1 else { return array }

  let middleIndex = array.count / 2
  
  let leftArray = mergeSort(Array(array[0..

This is the final version of the merge sort algorithm. Here's a summary of the key procedures of merge sort:

  1. The strategy of merge sort (and many other algorithms) is divide and conquer. You want to solve many small problems rather than one big problem.
  2. There are two core responsibilities - A method that handles dividing the initial array recursively, and a method that handles merging two arrays together.
  3. The merging function should take two sorted arrays and produce a single sorted array.

You can try this out for yourself by adding the following at the end of the playground:

mergeSort(array)

You should see a sorted array in the sidebar of the Playground:

[2, 3, 6, 7, 9]

Generic Swift Merge Sort Implementation

Now that you've written a merge sort function that handles integers, your next goal is to create a more robust merge sort that can handle all data types. You can achieve that easily with generics and luckily, it's only a minor change.

Find and replace all the Int declarations with T, and add <T: Comparable> after each function name. Your functions should look like this:

func mergeSort(_ array: [T]) -> [T] {
  guard array.count > 1 else { return array }

  let middleIndex = array.count / 2
  
  let leftArray = mergeSort(Array(array[0..(_ left: [T], _ right: [T]) -> [T] {
  var leftIndex = 0
  var rightIndex = 0

  var orderedArray: [T] = []
  
  while leftIndex < left.count && rightIndex < right.count {
    let leftElement = left[leftIndex]
    let rightElement = right[rightIndex]

    if leftElement < rightElement {
      orderedArray.append(leftElement)
      leftIndex += 1
    } else if leftElement > rightElement {
      orderedArray.append(rightElement)
      rightIndex += 1
    } else { 
      orderedArray.append(leftElement)
      leftIndex += 1
      orderedArray.append(rightElement)
      rightIndex += 1
    }
  }

  while leftIndex < left.count {
    orderedArray.append(left[leftIndex])
    leftIndex += 1
  }

  while rightIndex < right.count {
    orderedArray.append(right[rightIndex])
    rightIndex += 1
  }
  
  return orderedArray
}

As long as the elements you're trying to sort is Comparable, i.e. you can use comparison operators < and >, you'll be able use merge sort.

Where To Go From Here?

I hope you enjoyed this tutorial on the merge sort algorithm!

Here is a playground with the above code. You can also find the original implementation and further discussion in the merge sort section of the Swift Algorithm Club repository.

This was just one of the many algorithm clubs focused on the Swift Algorithm Club repository. If you're interested in more, check out the repo.

It's in your best interest to know about algorithms and data structures - they're solutions to many real world problems, and are frequently asked as interview questions. Plus it's fun!

So stay tuned for many more tutorials from the Swift Algorithm club in the future. In the meantime, if you have any questions on implementing trees in Swift, please join the forum discussion below!

Note: The Swift Algorithm Club is always looking for more contributors. If you've got an interesting data structure, algorithm, or even an interview question to share, don't hesitate to contribute! To learn more about the contribution process, check out our Join the Swift Algorithm Club article.
Kelvin Lau

Kelvin is a physicist turned Swift iOS Developer. He's also one of the two maintainers for the Swift Algorithm Club. While he's currently entrenched with iOS development, he often reminisces of his aspirations to be part of the efforts in space exploration.

Outside of programming work, he's an aspiring entrepreneur and musician. You can find him on his twitter at @KelvinlauKL

Other Items of Interest

Save time.
Learn more with our video courses.

raywenderlich.com Weekly

Sign up to receive the latest tutorials from raywenderlich.com each week, and receive a free epic-length tutorial as a bonus!

Advertise with Us!

PragmaConf 2016 Come check out Alt U

Our Books

Our Team

Video Team

... 19 total!

Swift Team

... 15 total!

iOS Team

... 34 total!

Android Team

... 15 total!

macOS Team

... 11 total!

Apple Game Frameworks Team

... 12 total!

Unity Team

... 10 total!

Articles Team

... 11 total!

Resident Authors Team

... 15 total!