Home » Kotlin

Program for Merge Sort in Kotlin

In this article, we are going to learn how to implement Merge sort in Kotlin? Here you will find what is merge sort, its algorithm, and program in Kotlin.
Submitted by Aman Gautam, on December 17, 2017

Merge sort is a sorting algorithm which uses Divide and Conquer approach. In this approach, the problem is divided into smaller subproblems similar to the original problem. Then solve them recursively, and then combine the results to find the solution to the original problem. Merge sort is faster algorithm than insertion sort or selection sort that we learned in the previous articles.

Algorithms

    MERGE_SORT(A,p,r)
    1.	if(p<r)
    2.	q=(p+r)/2
    3.	merge_sort(A,p,q)
    4.	merge_sort(A,q+1,r)
    5.	merge(A,p,q,r)


    MERGE(A,p,q,r)
    1.	n1 = q-p+1
    2.	n2 = r-q
    3.	create array L[0..n1] and R[0..n2]
    4.	fori = 0 to n1)
    5.	L[i]=A[p+i]
    6.	for j = 0 to n2)
    7.	    R[j]=A[q+j]
    8.	i=0
    9.	j=0
    10.	for k = p to r 
    11.	    if(L[i]<=R[j])
    12.	A[k]=L[i]
    13.	i=i+1
    14.	    else
    15.	A[k]=R[j]
    16.	        j=j+1

Algorithm source from Introduction to Algorithms by cormen

This algorithm takes O(nlog(n)) time. In this, the unsorted array is broken into subarrays of smaller size (till each subarray of size one), then each subarray is sorted one by one and then we merge all subarrays to get required a sorted array. This is a stable sorting algorithm, but not in place as it requires n additional spaces.

Program to implement Merge Sort in Kotlin

fun merge(A: Array<Int>, p: Int, q: Int, r: Int) {
    var left = A.copyOfRange(p, q + 1)
    var right = A.copyOfRange(q + 1, r + 1)
    var i = 0
    var j = 0

    for (k in p..r) {
        if ((i <= left.size - 1) && ((j >= right.size) || (left[i] <= right[j]))) {
            A[k] = left[i];
            i++;
        } else {
            A[k] = right[j];
            j++;
        }
    }
}

fun merge_sort(A: Array<Int>, p: Int, r: Int) {
    if (p < r) {
        var q = (p + r) / 2
        merge_sort(A, p, q)
        merge_sort(A, q + 1, r)
        merge(A, p, q, r)
    }
}

fun main(arg: Array<String>) {
    print("Enter no. of elements :")
    var n = readLine()!!.toInt()

    println("Enter elements : ")
    var A = Array(n, { 0 })
    for (i in 0 until n)
        A[i] = readLine()!!.toInt()

    merge_sort(A, 0, A.size - 1)

    println("Sorted array is : ")
    for (i in 0 until n)
        print("${A[i]}  ")
}

Output

Enter no. of elements :5
Enter elements :
23
45
65
23
21
Sorted array is :
21  23  23  45  65