Thursday, July 18, 2024
HomeAlgorithmsMerge sort Kotlin Implementation - Sorting Algorithms #3

Merge sort Kotlin Implementation – Sorting Algorithms #3


Merge Sort is sorting based on Divide and Conquer strategy and is one of the famous algorithms among Sorting. In this article, we will be discussing about Merge Sort Kotlin Implementation.

How Merge sort Works?

Merge sort algorithm technique basically involves two processes – one process splits the array into two halves and sorts them individually. The other process involves merging them again into a single array. This first process of splitting the array goes on and on and on till the array divides into small subfiles with single elements and later merged. Thus it does not need separate stack.

Related Links

Let us quickly dive into the Merge sort kotlin implementation. In addition to commenting the code wherever its necessary, I tried to explain in brief at the bottom of the implementation for those who seek more info.

package main.dataStructures.sorting
fun main(args: Array<String>) {
val array = readLine()!!.split(" ").map { it.toInt() }.toIntArray() // 1) Read the input and split into array
for(i in array) println(i)
fun mergeSort(array : IntArray, helper:IntArray = IntArray(array.size), low:Int = 0, high : Int = array.size-1) {
if(low < high) {
val middle:Int = (low+high)/2 // 2) calculating the middle element
mergeSort(array, helper, low, middle) // 3) to sort left half
mergeSort(array, helper, middle+1, high) // 4) to sort right half
merge(array, helper, low, middle, high) // 5) Merge them
fun merge (array: IntArray, helper: IntArray, low: Int, middle:Int, high: Int){
// a) copying both halves into helper array
for(i in low..high) helper[i] = array[i]
var helperLeft = low
var helperRight = middle + 1 // b) helper variables
var current = low
/*Iterate through helper array. Compare the left and right half, copying back the smaller element
* from the two halves into original array*/
while (helperLeft <= middle && helperRight <= high) { // c) condition to check helper left and helper right
if(helper[helperLeft] <= helper[helperRight]) { // d) Check if value at helperLeft index is less than that of value at helper right
array[current] = helper[helperLeft]
} else { // e) right element is smaller than left element
array[current] = helper[helperRight]
// f) copy the rest of leftside of array into target
val remaining = middle – helperLeft
for (i in 0..remaining) {
array[current + i] = helper[helperLeft + i]

view raw


hosted with ❤ by GitHub

Code Explanation for Merge Sort Kotlin Algorithm

  1. Read the Input and Split into array: Here we are trying to read the input whose values are separated by spaces(for eg., 5 4 3 2 1) and later converting them into an array of integers. Next, mergeSort() function is called in 5th Line.
  2. Calculating the middle element: To split the array into two halves we are calculating and splitting array into two halves – 0 to middle, middle + 1 to array.length-1
  3. To sort left half: Recursively calling mergeSort() function on the left half to make it sorted
  4. To sort right half: Recursively calling mergeSort() function on the right half to make it sorted
  5. Merge them: Here we are calling merge() function which takes few parameters as shown to help them sort and merge. We added additional points in this function. Lets see them individually
    1. Copying both halves into helper array: Here we are copying both halves into helper array.
    2. Helper variables: helperLeft and helperRight keeps the track of where the start of left and right halves is.
    3. Condition to check helper left and helper right: checking if both the helper variables are within the limits
    4. Check if value at helperLeft index is less than that of value at helper right: If it’s true, then we’ll fill the current position of array with the element present at helperLeft index and increment the helperLeft to compare with other right elements in next iteration.
    5. Right element is smaller than left element: If the right value is true, we’ll perform a similar operation as that of the above.
    6. Copy the rest of left side of array into target: Here we will be copying any elements which are left in the left side of array after merging. We don’t copy the right half because they will be already be present at their respective spots. For example if we take the values as [1, 4, 5, || 3, 9, 10] before merging the elements left will be [9, 10] which will be present at last place both in helper array and our array. Hence no need to copy them.


Here the Runtime for merge sort is O(n log n) for average and worst cases.

In the next article, we will be looking into other few major sorting techniques.

Want to improve this article / contribute new articles? Reach us at –


Please enter your comment!
Please enter your name here

This site uses Akismet to reduce spam. Learn how your comment data is processed.


Packages in Java

Hello World! Today's blog is about packages in java. Here, we will learn about what are packages and how we can use packages along with...

House Robber Problem | Maximum Sum of non-adjacent elements

In this blog post, we will discuss about how to find maximum sum of Non-Adjacent elements. Since House Robber Problem is a typical DP Problem...

Check Array Formation Through Concatenation | Leetcode Problem 1640

In this video, we will explain Check Array Formation Through Concatenation, Leetcode's 1640th problem in 2 different approaches along with a coding solution. Problem statement You are given...

Binary Tree Traversals in Kotlin – PreOrder, InOrder and PostOrder Traversals

Binary Tree Traversals are most common Tree Problems in an Interview as well as Competitive Programming. They can be efficient while searching, inserting and deleting...

Follow us


Most Popular