Merge Sort in Kotlin

Merge sort is a popular sorting algorithm that works by recursively dividing an array into smaller sub-arrays until each sub-array has only one element, and then merging the sub-arrays back together in sorted order. The merging process involves comparing the first element of each sub-array and adding the smaller of the two elements to a new array, and then repeating the process until all elements have been added to the new array.

fun mergeSort(arr: IntArray): IntArray {
    if (arr.size <= 1) {
        return arr
    }
    val mid = arr.size / 2
    val left = arr.sliceArray(0 until mid)
    val right = arr.sliceArray(mid until arr.size)
    return merge(mergeSort(left), mergeSort(right))
}

The mergeSort function takes an array of integers arr and returns a new array of integers in sorted order. The function recursively splits the input array into two sub-arrays, each containing roughly half of the elements, until each sub-array contains only one element. The function then calls the merge function to merge the two sub-arrays back together in sorted order.

fun merge(left: IntArray, right: IntArray): IntArray {
    var i = 0
    var j = 0
    val result = IntArray(left.size + right.size)
    var k = 0
    while (i < left.size && j < right.size) {
        if (left[i] <= right[j]) {
            result[k++] = left[i++]
        } else {
            result[k++] = right[j++]
        }
    }
    while (i < left.size) {
        result[k++] = left[i++]
    }
    while (j < right.size) {
        result[k++] = right[j++]
    }
    return result
}

The merge function takes two arrays of integers left and right and returns a new array of integers in sorted order. The function creates a new array result of length left.size + right.size to store the merged sub-arrays. The function compares the first element of each sub-array and adds the smaller of the two elements to the result array. The function then repeats this process until all elements have been added to the result array.

Merge sort has a time complexity of O(n log n), where n is the number of elements in the array. This means that the time it takes to sort an array using merge sort increases logarithmically with the size of the array. However, merge sort has a space complexity of O(n), as it creates new arrays to store the sub-arrays during the sorting process. In practice, merge sort is often used for sorting linked lists, as it can efficiently merge two sorted lists into a single sorted list.

fun main() {
    val arr = intArrayOf(20, 15, 81, 12, 6)
	val arrSorted = mergeSort(arr)
    for(i in 1 until arrSorted.size)
		println(arrSorted[i])
}

fun mergeSort(arr: IntArray): IntArray {
    if (arr.size <= 1) {
        return arr
    }
    val mid = arr.size / 2
    val left = arr.sliceArray(0 until mid)
    val right = arr.sliceArray(mid until arr.size)
    return merge(mergeSort(left), mergeSort(right))
}

fun merge(left: IntArray, right: IntArray): IntArray {
    var i = 0
    var j = 0
    val result = IntArray(left.size + right.size)
    var k = 0
    while (i < left.size && j < right.size) {
        if (left[i] <= right[j]) {
            result[k++] = left[i++]
        } else {
            result[k++] = right[j++]
        }
    }
    while (i < left.size) {
        result[k++] = left[i++]
    }
    while (j < right.size) {
        result[k++] = right[j++]
    }
    return result
}