In this source code example, we will write a code to implement the Merge Sort algorithm in Kotlin.
Merge sort is one of the most efficient sorting algorithms. With a time complexity of O(n log n), it’s one of the fastest of all general-purpose sorting algorithms. The idea behind merge sort is divide and conquer — to break a big problem into several smaller, easier-to-solve problems, and then combine those solutions into a final result. The merge sort mantra is to split first and merge after.
Merge Sort Algorithm in Kotlin
Let's write the Kotlin program to Sort an Array of elements in ascending order:
import java.util.*
fun <E: Comparable<E>> Array<E>.sort(): Array<E> {
if (size <= 1) return this
val middle = size / 2
val left = copyOfRange(0, middle)
val right = copyOfRange(middle, size)
return merge(this, left.sort(), right.sort())
}
private fun <E: Comparable<E>> merge(arr: Array<E>, left: Array<E>, right: Array<E>): Array<E> {
val leftArrSize = left.size
val rightArrSize = right.size
var leftArrIndex = 0
var rightArrIndex = 0
var index = 0
while(leftArrIndex < leftArrSize && rightArrIndex < rightArrSize) {
if (left[leftArrIndex] <= right[rightArrIndex]) {
arr[index] = left[leftArrIndex]
leftArrIndex++
} else {
arr[index] = right[rightArrIndex]
rightArrIndex++
}
index++
}
while(leftArrIndex < leftArrSize) {
arr[index] = left[leftArrIndex]
leftArrIndex++
index++
}
while(rightArrIndex < rightArrSize) {
arr[index] = right[rightArrIndex]
rightArrIndex++
index++
}
return arr
}
fun main(args: Array<String>) {
val nums = arrayOf(2, 12, 89, 23, 76, 43, 12)
nums.sort()
println(Arrays.toString(nums))
val languages = arrayOf("Kotlin", "Java", "C#", "R", "Python", "Scala", "Groovy", "C", "C++")
val sortedLanguages = languages.sort()
println(Arrays.toString(languages))
}
Output:
[2, 12, 12, 23, 43, 76, 89]
[C, C#, C++, Groovy, Java, Kotlin, Python, R, Scala]
Comments
Post a Comment