Swift Algorithm Club: Swift Merge Sort

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.

[spoiler]

while leftIndex < left.count && rightIndex < right.count {
  // 1
  let leftElement = left[leftIndex]
  let rightElement = right[rightIndex]

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

This should be relatively straightforward:

1. Use leftIndex and rightIndex to extract the elements for comparison.
2. If the element on the left is less than the element on the right, you'll add that to the orderedArray and increment the leftIndex.
3. If the element on the left is greater than the element on the right, you'll add that to the orderedArray and increment the rightIndex.
4. In the case that both elements are equal, you simply append both to orderedArray and increment both indexes.

[/spoiler]

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..<middleIndex]))
  let rightArray = mergeSort(Array(array[middleIndex..<array.count]))
  
  // here
  return merge(leftArray, rightArray)
}

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<T: Comparable>(_ array: [T]) -> [T] {
  guard array.count > 1 else { return array }

  let middleIndex = array.count / 2
  
  let leftArray = mergeSort(Array(array[0..<middleIndex]))
  let rightArray = mergeSort(Array(array[middleIndex..<array.count]))
  
  return merge(leftArray, rightArray)
}

func merge<T: Comparable>(_ 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 to 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 algorithms in 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!

If you enjoyed what you learned in this tutorial, why not check out our Data Structures and Algorithms in Swift book, available on our store?

In Data Structures and Algorithms in Swift, you’ll learn how to implement the most popular and useful data structures and when and why you should use one particular datastructure or algorithm over another. This set of basic data structures and algorithms will serve as an excellent foundation for building more complex and special-purpose constructs.

As well, the high-level expressiveness of Swift makes it an ideal choice for learning these core concepts without sacrificing performance.

• You’ll start with the fundamental structures of linked lists, queues and stacks, and see how to implement them in a highly Swift-like way.
• Move on to working with various types of trees, including general purpose trees, binary trees, AVL trees, binary search trees and tries.
• Go beyond bubble and insertion sort with better-performing algorithms, including mergesort, radix sort, heap sort and quicksort.
• Learn how to construct directed, non-directed and weighted graphs to represent many real-world models, and traverse graphs and trees efficiently with breadth-first, depth-first, Dijkstra’s and Prim’s algorithms to solve problems such as finding the shortest path or lowest cost in a network.
• And much, much more!

By the end of this book, you’ll have hands-on experience solving common issues with data structures and algorithms — and you’ll be well on your way to developing your own efficient and useful implementations.