Merge Sort

fun main() {
    val arr = intArrayOf(2, 1, 4, 10).toTypedArray()
    mergeSort(arr)
    println(arr.contentToString())
}

fun mergeSort(arr: Array<Int>) {
    if (arr.isEmpty() || arr.size == 1) return
    val mid = arr.size.div(2)
    val left = arr.copyOfRange(0, mid)
    val right = arr.copyOfRange(mid, arr.size)
    mergeSort(left)
    mergeSort(right)
    merge(left, right, arr)
}

fun merge(left: Array<Int>, right: Array<Int>, result: Array<Int>) {
    var leftIndex = 0
    var rightIndex = 0

    for (index in result.indices) {
        when {
            leftIndex == left.size && rightIndex == right.size -> {
                break
            }

            leftIndex == left.size -> {
                result[index] = right[rightIndex++]
            }

            rightIndex == right.size && leftIndex < left.size -> {
                result[index] = left[leftIndex++]
            }

            left[leftIndex] < right[rightIndex] -> {
                result[index] = left[leftIndex++]
            }

            else -> {
                result[index] = right[rightIndex++]
            }
        }
    }
}