Merge Sort in Kotlin

Posted on August 4, 2017  •  2 minutes  • 360 words

I’m learning Kotlin. It’s a statically typed programming language developed by JetBrains running on the JVM. I believe Kotlin has a great future on Android, because it`s offering a lot of functions that Java is missing and i think Google wouldn’t officially support it if they think otherwise. Spring Boot also supports Kotlin. Recently Jake Wharton announced that he is working on Kotlin at Google. He’s involved in the libraries like Retrofit, ButterKnife and RxJava.

Today is my first day at @Google! I've joined the @Android Framework team to work on @Kotlin stuff.

— Jake Wharton (@JakeWharton) 7. August 2017

A few days ago i read a blog post (Merge Sort in Swift) of my colleague Thomas Hanning. And i wanted to find out how a merge sort in Kotlin would look like.

What is merge sort?

Merge Sort was invented by John von Neumann in 1945, and is an algorithm of class to the “divide and conquer”. Meaning, the algorithm splits an input into various pieces, sorts them and then merges them back together.

fun main(args: Array<String>) {
    val numbers = mutableListOf(38,27,43,3,9,82,10)
    val sortedList = mergeSort(numbers)
    println("Unsorted: $numbers")
    println("Sorted: $sortedList")
}

//Log output
Unsorted: [38, 27, 43, 3, 9, 82, 10]
Sorted: [3, 9, 10, 27, 38, 43, 82]

fun mergeSort(list: List<Int>): List<Int> {
    if (list.size <= 1) {
        return list
    }

    val middle = list.size / 2
    var left = list.subList(0,middle);
    var right = list.subList(middle,list.size);

    return merge(mergeSort(left), mergeSort(right))
}

The function mergeSort() gets a list and splits at the middle into two new lists. This lists will be passed to mergeSort again until there only lists with one item.

fun merge(left: List<Int>, right: List<Int>): List<Int>  {
    var indexLeft = 0
    var indexRight = 0
    var newList : MutableList<Int> = mutableListOf()

    while (indexLeft < left.count() && indexRight < right.count()) {
        if (left[indexLeft] <= right[indexRight]) {
            newList.add(left[indexLeft])
            indexLeft++
        } else {
            newList.add(right[indexRight])
            indexRight++
        }
    }

    while (indexLeft < left.size) {
        newList.add(left[indexLeft])
        indexLeft++
    }

    while (indexRight < right.size) {
        newList.add(right[indexRight])
        indexRight++
    }
   
    return newList;
}

The function merge sorts two lists and merge it into a new list.

Example Project