Chapters

Hide chapters

Data Structures & Algorithms in Swift

Third Edition · iOS 13 · Swift 5.1 · Xcode 11

Before You Begin

Section 0: 3 chapters
Show chapters Hide chapters

28. Merge Sort
Written by Kelvin Lau

Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as scrambled text.

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:

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

  1. Finally, merge the piles together in the reverse order in which you split them. During each merge, you put the contents in sorted order. This is easy because each individual pile has already been 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
}
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
}

Merge

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

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
}

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 together.

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)
}
example(of: "merge sort") {
  let array = [7, 2, 6, 3, 9]
  print("Original: \(array)")
  print("Merge sorted: \(mergeSort(array))")
}
---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:

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.
Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.
© 2024 Kodeco Inc.

You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a Kodeco Personal Plan.

Unlock now