28. Merge Sort

Written by Kelvin Lau

Merge sort is one of the most efficient sorting algorithms. With a time complexity of O(n log n), it’s one of the fastest of all general-purpose sorting algorithms. The idea behind merge sort is divide and conquer — to break up a big problem into several smaller, easier-to-solve problems and then combine those solutions into a final result. The merge sort mantra is to split first and merge after. In this chapter, you’ll implement merge sort from scratch. Let’s start with an example.

Example

Assume that you’re given a pile of unsorted playing cards:

The merge sort algorithm works as follows:

1. First, split the pile in half. You now have two unsorted piles:

2. Now, keep splitting the resulting piles until you can’t split anymore. In the end, you will have one (sorted!) card in each pile:

3. Finally, merge the piles in the reverse order in which you split them. During each merge, you put the contents in sorted order. This process is easy because each pile is already sorted:

Implementation

Open up the starter playground to get started.

Split

In the Sources folder in your playground, create a new file named MergeSort.swift. Write the following inside the file:

public func mergeSort<Element>(_ array: [Element])
    -> [Element] where Element: Comparable {
  let middle = array.count / 2
  let left = Array(array[..<middle])
  let right = Array(array[middle...])
  // ... more to come
}

Here, you split the array into halves. Splitting once isn’t enough. However, you have to keep splitting recursively until you can’t split any more, which is when each subdivision contains just one element.

To do this, update mergeSort as follows:

public func mergeSort<Element>(_ array: [Element])
    -> [Element] where Element: Comparable {
  // 1
  guard array.count > 1 else {
    return array
  }
  let middle = array.count / 2
  // 2
  let left = mergeSort(Array(array[..<middle]))
  let right = mergeSort(Array(array[middle...]))
  // ... more to come
}

You’ve made two changes here:

1. Recursion needs a base case, which you can also think of as an “exit condition.” In this case, the base case is when the array only has one 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’ll try to split again.

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

Merge

Your final step is to merge the left and right arrays. To keep things clean, you will create a separate merge function for this.

The sole responsibility of the merging function is to take in two sorted arrays and combine them while retaining the sort order. Add the following just below the mergeSort function:

private func merge<Element>(_ left: [Element], _ right: [Element])
    -> [Element] where Element: Comparable {
  // 1
  var leftIndex = 0
  var rightIndex = 0
  // 2
  var result: [Element] = []
  // 3
  while leftIndex < left.count && rightIndex < right.count {
    let leftElement = left[leftIndex]
    let rightElement = right[rightIndex]
    // 4
    if leftElement < rightElement {
      result.append(leftElement)
      leftIndex += 1
    } else if leftElement > rightElement {
      result.append(rightElement)
      rightIndex += 1
    } else {
      result.append(leftElement)
      leftIndex += 1
      result.append(rightElement)
      rightIndex += 1
    }
  }
  // 5
  if leftIndex < left.count {
    result.append(contentsOf: left[leftIndex...])
  }
  if rightIndex < right.count {
    result.append(contentsOf: right[rightIndex...])
  }
  return result
}

Here’s what’s going on:

1. The leftIndex and rightIndex variables track your progress as you parse through the two arrays.
2. The result array will house the combined array.
3. Starting from the beginning, you sequentially compare the elements in the left and right arrays. If you’ve reached the end of either array, there’s nothing else to compare.
4. The smaller of the two elements go into the result array. If the elements were equal, they can both be added.
5. The first loop guarantees that either left or right is empty. Since both arrays are sorted, this ensures that the leftover elements are greater than or equal to the ones currently in result. In this scenario, you can append the rest of the elements without comparison.

Finishing up

Complete the mergeSort function by calling merge. Because you call mergeSort recursively, the algorithm will split and sort both halves before merging them.

public func mergeSort<Element>(_ array: [Element])
    -> [Element] where Element: Comparable {
  guard array.count > 1 else {
    return array
  }
  let middle = array.count / 2
  let left = mergeSort(Array(array[..<middle]))
  let right = mergeSort(Array(array[middle...]))
  return merge(left, right)
}

This code 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 is to divide and conquer so that you solve many small problems instead of one big problem.

2. It has two core responsibilities: a method to divide the initial array recursively and a method to merge two arrays.

3. The merging function should take two sorted arrays and produce a single sorted array.

Finally — time to see this in action. Head back to the main playground page and test your merge sort with the following:

example(of: "merge sort") {
  let array = [7, 2, 6, 3, 9]
  print("Original: \(array)")
  print("Merge sorted: \(mergeSort(array))")
}

This outputs:

---Example of merge sort---
Original: [7, 2, 6, 3, 9]
Merge sorted: [2, 3, 6, 7, 9]

Performance

The best, worst and average time complexity of merge sort is O(n log n), which isn’t too bad. If you’re struggling to understand where n log n comes from, think about how the recursion works:

• In general, if you have an array of size n, the number of levels is log2(n). As you recurse, you split a single array into two smaller arrays. This means an array of size two will need one recursion level, an array of size four will need two levels, an array of size eight will need three levels, and so on. If you had an array of 1,024 elements, it would take ten levels of recursively splitting in two to get down to 1024 single element arrays.
• The cost of a single recursion is O(n). A single recursion level will merge n elements. It doesn’t matter if there are many small merges or one large one; the number of elements merged will still be n at each level.

This brings the total cost to O(log n) × O(n) = O(n log n).

The previous chapter’s sort algorithms were in-place and used swapAt to move elements around. Merge sort, by contrast, allocates additional memory to do its work. How much? There are log2(n) levels of recursion, and at each level, n elements are used. That makes the total O(n log n) in space complexity. Merge sort is one of the hallmark sorting algorithms. It’s relatively simple to understand and serves as a great introduction to how divide-and-conquer algorithms work. Merge sort is O(n log n), and this implementation requires O(n log n) of space. If you are clever with your bookkeeping, you can reduce the memory required to O(n) by discarding the memory that is not actively being used.

Key points

• Merge sort is in the category of the divide-and-conquer algorithms.
• There are many implementations of merge sort, and you can have different performance characteristics depending on the implementation.