Home Android & Kotlin Books Data Structures & Algorithms in Kotlin

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 scrambled text.

You can unlock the rest of this book, and our entire catalogue of books and videos, with a raywenderlich.com Professional subscription.

Unlock Now

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:

  1. Split the pile in half, which gives you two unsorted piles:

  1. 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:

  1. 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 of Comparator<T>.
16. Radix Sort 14. O(n²) Sorting Algorithms

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.

Have feedback to share about the online reading experience? If you have feedback about the UI, UX, highlighting, or other features of our online readers, you can send them to the design team with the form below:

© 2021 Razeware LLC

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 raywenderlich.com Professional subscription.

Unlock Now

To highlight or take notes, you’ll need to own this book in a subscription or purchased by itself.

Read for Free with a Subscription

Buy this book for $59.99