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.
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.
Learn more about bidirectional Unicode characters
| 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 | |
| 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] | |
| } | |
| } |
Code Explanation for Merge Sort Kotlin Algorithm
- 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.
- 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
- To sort left half: Recursively calling mergeSort() function on the left half to make it sorted
- To sort right half: Recursively calling mergeSort() function on the right half to make it sorted
- 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
- Copying both halves into helper array:Â Here we are copying both halves into helper array.
- Helper variables:Â helperLeft and helperRight keeps the track of where the start of left and right halves is.
- Condition to check helper left and helper right:Â checking if both the helper variables are within the limits
- 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.
- Right element is smaller than left element: If the right value is true, we’ll perform a similar operation as that of the above.
- 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/
