15.
Merge Sort
Written by Matei Suica, Kelvin Lau and Vincent Ngo
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 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.
As an example, assume that you’re given a pile of unsorted playing cards:
The merge sort algorithm works as follows:
- Split the pile in half, which gives you two unsorted piles:
- Keep splitting the resulting piles until you can’t split them anymore. In the end, you’ll have one card in each pile. Because a single card is always sorted, you now have a bunch of sorted piles:
- Merge the piles in the reverse order in which you split them. During each merge, put the contents in sorted order. This is easy because each pile has already been sorted. You know that the smallest cards in any pile are on the left side:
In this chapter, you’ll implement merge sort from scratch.
Implementation
The Merge sort consists of two main steps: split and merge. To implement them, open the starter project and start editing the MergeSort.kt file into the mergesort package.
Split
In the MergeSort.kt file copy the following code:
fun <T : Comparable<T>> List<T>.mergeSort(): List<T> {
if (this.size < 2) return this
val middle = this.size / 2
val left = this.subList(0, middle)
val right = this.subList(middle, this.size)
// ... more to come
}
fun <T : Comparable<T>> List<T>.mergeSort(): List<T> {
// 1
if (this.size < 2) return this
val middle = this.size / 2
// 2
val left = this.subList(0, middle).mergeSort()
val right = this.subList(middle, this.size).mergeSort()
// ... still more to come
}
Merge
Your final step is to merge the left and right lists. To keep things clean, you’ll create a separate merge function to handle this.
private fun <T : Comparable<T>> merge(left: List<T>, right: List<T>): List<T> {
// 1
var leftIndex = 0
var rightIndex = 0
// 2
val result = mutableListOf<T>()
// 3
while (leftIndex < left.size && rightIndex < right.size) {
val leftElement = left[leftIndex]
val rightElement = right[rightIndex]
// 4
if (leftElement < rightElement) {
result.add(leftElement)
leftIndex += 1
} else if (leftElement > rightElement) {
result.add(rightElement)
rightIndex += 1
} else {
result.add(leftElement)
leftIndex += 1
result.add(rightElement)
rightIndex += 1
}
}
// 5
if (leftIndex < left.size) {
result.addAll(left.subList(leftIndex, left.size))
}
if (rightIndex < right.size) {
result.addAll(right.subList(rightIndex, right.size))
}
return result
}
Finishing up
Complete mergeSort by calling merge. Because you call mergeSort recursively, the algorithm will split and sort both halves before merging them.
fun <T : Comparable<T>> List<T>.mergeSort(): List<T> {
if (this.size < 2) return this
val middle = this.size / 2
val left = this.subList(0, middle).mergeSort()
val right = this.subList(middle, this.size).mergeSort()
return merge(left, right)
}
"merge sort" example {
val list = listOf(7, 2, 6, 3, 9)
println("Original: $list")
val result = list.mergeSort()
println("Merge sorted: $result")
}
---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:
Challenges
Challenge 1: Iterables merge
Write a function that takes two sorted iterables and merges them into a single iterable. Here’s the function signature to start:
fun <T : Comparable<T>> merge(
first: Iterable<T>,
second: Iterable<T>
): Iterable<T>
Solution 1
The tricky part of this challenge is the limited capabilities of Iterable. Traditional implementations of this algorithm rely on the abilities of List types to keep track of indices.
private fun <T> Iterator<T>.nextOrNull(): T? {
return if (this.hasNext()) this.next() else null
}
fun <T : Comparable<T>> merge(
first: Iterable<T>,
second: Iterable<T>
): Iterable<T> {
// 1
val result = mutableListOf<T>()
val firstIterator = first.iterator()
val secondIterator = second.iterator()
// 2
if (!firstIterator.hasNext()) return second
if (!secondIterator.hasNext()) return first
// 3
var firstEl = firstIterator.nextOrNull()
var secondEl = secondIterator.nextOrNull()
// 4
while (firstEl != null && secondEl != null) {
// more to come
}
}
when {
// 1
firstEl < secondEl -> {
result.add(firstEl)
firstEl = firstIterator.nextOrNull()
}
// 2
secondEl < firstEl -> {
result.add(secondEl)
secondEl = secondIterator.nextOrNull()
}
// 3
else -> {
result.add(firstEl)
result.add(secondEl)
firstEl = firstIterator.nextOrNull()
secondEl = secondIterator.nextOrNull()
}
}
while (firstEl != null) {
result.add(firstEl)
firstEl = firstIterator.nextOrNull()
}
while (secondEl != null) {
result.add(secondEl)
secondEl = secondIterator.nextOrNull()
}
return result
"merge iterables" example {
val list1 = listOf(1, 2, 3, 4, 5, 6, 7, 8)
val list2 = listOf(1, 3, 4, 5, 5, 6, 7, 7)
val result = merge(list1, list2)
println("Merge sorted: $result")
}
---Example of merge iterables---
Merge sorted: [1, 1, 2, 3, 3, 4, 4, 5, 5, 5, 6, 6, 7, 7, 7, 8]
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.
- To do a comparison, in this chapter you sorted objects implementing the
Comparable<T>interface but the same can be done providing a different implementation ofComparator<T>.