Kotlin Program for Merge Sort Algorithm Example

A Kotlin program for merge sort uses a mergeSort function that splits the list recursively and merges sorted halves using a merge function; for example, fun mergeSort(arr: IntArray): IntArray { if (arr.size <= 1) return arr; val mid = arr.size / 2; val left = mergeSort(arr.sliceArray(0 until mid)); val right = mergeSort(arr.sliceArray(mid until arr.size)); return merge(left, right) }.

Examples

Input[5, 3, 8, 4, 2]

Output[2, 3, 4, 5, 8]

Input[1]

Output[1]

Input[]

Output[]

How to Think About It

To sort an array using merge sort, first check if the array has one or no elements, which means it is already sorted. Otherwise, split the array into two halves, sort each half by calling the same function recursively, and then combine the two sorted halves by comparing elements one by one to create a fully sorted array.

Algorithm

1

Check if the array size is 1 or less; if yes, return the array as it is already sorted.

2

Find the middle index to split the array into two halves.

3

Recursively call merge sort on the left half.

4

Recursively call merge sort on the right half.

5

Merge the two sorted halves by comparing elements and return the merged sorted array.

Code

kotlin

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

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

fun main() {
    val array = intArrayOf(5, 3, 8, 4, 2)
    val sorted = mergeSort(array)
    println(sorted.joinToString(prefix = "[", postfix = "]"))
}

Output

[2, 3, 4, 5, 8]

Dry Run

Let's trace the array [5, 3, 8, 4, 2] through the merge sort code.

1

Initial call

Input array is [5, 3, 8, 4, 2], size > 1, so split into [5, 3] and [8, 4, 2].

2

Sort left half

Sort [5, 3]: split into [5] and [3], both size 1, so return as is.

3

Merge left half

Merge [5] and [3]: compare 5 and 3, merged array is [3, 5].

4

Sort right half

Sort [8, 4, 2]: split into [8] and [4, 2].

5

Sort right half's right half

Sort [4, 2]: split into [4] and [2], both size 1.

6

Merge right half's right half

Merge [4] and [2]: merged array is [2, 4].

7

Merge right half

Merge [8] and [2, 4]: merged array is [2, 4, 8].

8

Final merge

Merge [3, 5] and [2, 4, 8]: merged array is [2, 3, 4, 5, 8].

Step	Left Array	Right Array	Merged Result
1	[5, 3]	[8, 4, 2]
2	[5]	[3]	[3, 5]
3	[8]	[4, 2]
4	[4]	[2]	[2, 4]
5	[8]	[2, 4]	[2, 4, 8]
6	[3, 5]	[2, 4, 8]	[2, 3, 4, 5, 8]

Why This Works

Step 1: Divide the array

The code splits the array into two halves recursively until each sub-array has one or zero elements, which are naturally sorted.

Step 2: Merge sorted halves

The merge function combines two sorted arrays by comparing their elements one by one, ensuring the merged array is sorted.

Step 3: Recursive sorting

By recursively sorting and merging, the entire array becomes sorted efficiently without sorting the whole array at once.

Alternative Approaches

In-place merge sort

kotlin

fun mergeSortInPlace(arr: IntArray, left: Int, right: Int) {
    if (left >= right) return
    val mid = (left + right) / 2
    mergeSortInPlace(arr, left, mid)
    mergeSortInPlace(arr, mid + 1, right)
    mergeInPlace(arr, left, mid, right)
}

fun mergeInPlace(arr: IntArray, left: Int, mid: Int, right: Int) {
    val temp = IntArray(right - left + 1)
    var i = left
    var j = mid + 1
    var k = 0
    while (i <= mid && j <= right) {
        temp[k++] = if (arr[i] <= arr[j]) arr[i++] else arr[j++]
    }
    while (i <= mid) temp[k++] = arr[i++]
    while (j <= right) temp[k++] = arr[j++]
    for (index in temp.indices) {
        arr[left + index] = temp[index]
    }
}

fun main() {
    val arr = intArrayOf(5, 3, 8, 4, 2)
    mergeSortInPlace(arr, 0, arr.size - 1)
    println(arr.joinToString(prefix = "[", postfix = "]"))
}

This approach sorts the array in place without creating many new arrays, saving memory but making code more complex.

Using Kotlin List and functional style

kotlin

fun mergeSortList(list: List<Int>): List<Int> {
    if (list.size <= 1) return list
    val mid = list.size / 2
    val left = mergeSortList(list.subList(0, mid))
    val right = mergeSortList(list.subList(mid, list.size))
    return mergeLists(left, right)
}

fun mergeLists(left: List<Int>, right: List<Int>): List<Int> {
    var i = 0
    var j = 0
    val merged = mutableListOf<Int>()
    while (i < left.size && j < right.size) {
        if (left[i] <= right[j]) {
            merged.add(left[i++])
        } else {
            merged.add(right[j++])
        }
    }
    while (i < left.size) merged.add(left[i++])
    while (j < right.size) merged.add(right[j++])
    return merged
}

fun main() {
    val list = listOf(5, 3, 8, 4, 2)
    val sorted = mergeSortList(list)
    println(sorted)
}

This uses Kotlin's immutable lists and functional style, which is more readable but less memory efficient than arrays.

Complexity: O(n log n) time, O(n) space

Time Complexity

Merge sort divides the array into halves recursively (log n splits) and merges all elements (n per merge), resulting in O(n log n) time.

Space Complexity

Extra space is needed to store temporary arrays during merging, so space complexity is O(n). In-place variants can reduce this.

Which Approach is Fastest?

Standard merge sort with arrays is fast and simple; in-place merge sort saves memory but is more complex; functional style is readable but slower.

Approach	Time	Space	Best For
Standard merge sort (arrays)	O(n log n)	O(n)	Balanced speed and simplicity
In-place merge sort	O(n log n)	O(1) or O(n)	Memory-sensitive environments
Functional style with lists	O(n log n)	O(n)	Readability and immutability