mergesort.kt

/**
mergesort - following algorithms illuminated
joshskeen
**/

fun main(args: Array<String>) {
    val listOf = listOf(1, 11, 8, 2, 3, 7, 8, 9, 3)
    println(mergesort(listOf))
}

fun mergesort(list: List<Int>): List<Int> {
    if (list.size <= 1) {
        return list //already sorted!
    }
    val midpoint = list.size / 2
    val left = mergesort(list.subList(0, midpoint))
    val right = mergesort(list.subList(midpoint, list.size))
    return merge(left, right)
}


fun merge(leftList: List<Int>, rightList: List<Int>): List<Int> {
    var leftIndex = 0
    var rightIndex = 0
    val out = mutableListOf<Int>()
    while (leftIndex < leftList.size && rightIndex < rightList.size) {
        val left = leftList[leftIndex]
        val right = rightList[rightIndex]
        if (left <= right) {
            out.add(left)
            leftIndex++
        } else {
            out.add(right)
            rightIndex++
        }
    }
    (leftIndex until leftList.size).forEach {
        out.add(leftList[it])
    }
    (rightIndex until rightList.size).forEach {
        out.add(rightList[it])
    }

    return out
}