Easy Peasy Merge Sort in Kotlin

January 23, 2019

Merge Sort is an efficient, comparison oriented, general-use sorting algorithm. In many different interview scenarios, you will be asked to code some sort of sorting algorithm, here we will demonstrate how to implement merge sort. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output. Mergesort is a divide and conquer algorithm that was invented by John von Neumann in 1945.

Let's see how it's done:

fun <T:Comparable<T>>mergesort(items:MutableList<T>):MutableList<T>{
    // if the list is empty then we don't need to run the algorithm. 
    if (items.isEmpty()){
        return items
    }
     // Creating the merge function
     fun merge(left:MutableList<T>, right:MutableList<T>):MutableList<T>{
        var merged: MutableList<T> = arrayListOf<T>()
        // Run while the left and right is empty 
        while(!left.isEmpty() && !right.isEmpty()){
            // Temporary variable
            val temp:T
             // Check which of the array is has a smaller start and assign to temp variable
            if (left.first() < right.first()) {
                temp = left.removeAt(0)
            } else {
                temp = right.removeAt(0)
            }
            // Add to the merged list. 
            merged.add(temp)
        }
        // If we get here then one of the arrays is empty, we can add to merged list. 
        if (!left.isEmpty()) {
            merged.addAll(left)
        } 
        if (!right.isEmpty()) {
            merged.addAll(right)
        }
         return merged
    }

    // Set the pivot point to be in the middle.
    val pivot = items.count()/2
    
    // Recursively perform merge sort. 
    var left  = mergesort(items.subList(0, pivot))
    var right = mergesort(items.subList(pivot, items.count()-1))
    
    // Generate the merged results. 
    return merge(left, right)
}