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 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:
- First, split the pile in half. You now have two unsorted piles:
- Now, keep splitting the resulting piles until you can’t split anymore. In the end, you will have one (sorted!) card in each pile:
- 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
}
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. 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.
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.