In this tutorial, we will write a Program to implement the Merge Sort algorithm in Kotlin programming language.
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]
Related Data Structures and Algorithms in Kotlin
- Bubble Sort Algorithm in Kotlin
- Heap Sort Algorithm in Kotlin
- Insertion Sort Algorithm in Kotlin
- Merge Sort Algorithm in Kotlin
- Quick Sort Algorithm in Kotlin
- Selection Sort Algorithm in Kotlin
- Stack Data Structure Implementation in Kotlin
- Queue Data Structure Implementation in Kotlin
- Deque Implementation in Kotlin
- Singly Linked List Implementation in Kotlin
- Doubly Linked List Implementation in Kotlin
- Circular Linked List Implementation in Kotlin
- Bubble Sort Algorithm in Kotlin
- Heap Sort Algorithm in Kotlin
- Insertion Sort Algorithm in Kotlin
- Merge Sort Algorithm in Kotlin
- Quick Sort Algorithm in Kotlin
- Selection Sort Algorithm in Kotlin
- Stack Data Structure Implementation in Kotlin
- Queue Data Structure Implementation in Kotlin
- Deque Implementation in Kotlin
- Singly Linked List Implementation in Kotlin
- Doubly Linked List Implementation in Kotlin
- Circular Linked List Implementation in Kotlin
Free Spring Boot Tutorial | Full In-depth Course | Learn Spring Boot in 10 Hours
Watch this course on YouTube at Spring Boot Tutorial | Fee 10 Hours Full Course
Comments
Post a Comment