Sunday, October 1, 2023
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.

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.

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 package main.dataStructures.sorting fun main(args: Array) { val array = readLine()!!.split(" ").map { it.toInt() }.toIntArray() // 1) Read the input and split into array mergeSort(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] helperLeft++ } else { // e) right element is smaller than left element array[current] = helper[helperRight] helperRight++ } current++ } // 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

MergeSort.kt

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.

#### Performance

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 – http://13.126.215.213.xip.io/test/write-an-article/

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...
00:11:41

### 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...

1,358Fans
10Followers
400Subscribers

00:11:41