Sorting is one of the most important operations in programming. Whether you’re working with numbers, words, or complex data, sorting helps organize information so it can be searched, displayed, or processed more efficiently. One of the most reliable and efficient sorting techniques is Merge Sort. It’s known for its divide-and-conquer approach, which makes it faster than many basic algorithms like Bubble Sort or Insertion Sort.
with hands-on learning.
get the skills and confidence to land your next move.
Merge Sort works by dividing the array into smaller subarrays, sorting each subarray individually, and then merging them back together in the correct order. This method ensures consistent performance even with large datasets. While the idea might sound complicated at first, once you understand the steps, it becomes quite logical and elegant. In this article, we’ll walk through several Kotlin programs that show how Merge Sort works — from simple recursive implementations to slightly more advanced and optimized versions. Everything will be explained clearly so that even a beginner can follow along with confidence.
Program 1: Basic Merge Sort using Recursion
This is the standard implementation of Merge Sort in Kotlin. It uses recursion to divide the array into halves and then merges them in sorted order.
fun mergeSort(arr: IntArray): IntArray {
if (arr.size <= 1) return arr
val middle = arr.size / 2
val left = mergeSort(arr.sliceArray(0 until middle))
val right = mergeSort(arr.sliceArray(middle until arr.size))
return merge(left, right)
}
fun merge(left: IntArray, right: IntArray): IntArray {
var i = 0
var j = 0
val merged = mutableListOf<Int>()
while (i < left.size && j < right.size) {
if (left[i] <= right[j]) {
merged.add(left[i])
i++
} else {
merged.add(right[j])
j++
}
}
while (i < left.size) merged.add(left[i++])
while (j < right.size) merged.add(right[j++])
return merged.toIntArray()
}
fun main() {
val numbers = intArrayOf(38, 27, 43, 3, 9, 82, 10)
println("Original Array: ${numbers.joinToString()}")
val sortedArray = mergeSort(numbers)
println("Sorted Array: ${sortedArray.joinToString()}")
}In this program, the mergeSort function keeps dividing the array into smaller parts until only one element remains in each. Then, the merge function combines these small parts back together in sorted order. This recursive process continues until the entire array is sorted. Beginners often find this version the most intuitive because it clearly shows how recursion breaks down and rebuilds the problem step by step.
Program 2: Merge Sort with Helper Function and In-Place Merging
In this version, we use a helper function and merge the elements directly into a temporary array before copying them back. It’s slightly more memory-efficient and a good way to see how in-place merging works.
fun mergeSortInPlace(arr: IntArray, left: Int, right: Int) {
if (left >= right) return
val mid = (left + right) / 2
mergeSortInPlace(arr, left, mid)
mergeSortInPlace(arr, mid + 1, right)
mergeInPlace(arr, left, mid, right)
}
fun mergeInPlace(arr: IntArray, left: Int, mid: Int, right: Int) {
val temp = IntArray(right - left + 1)
var i = left
var j = mid + 1
var k = 0
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++]
} else {
temp[k++] = arr[j++]
}
}
while (i <= mid) temp[k++] = arr[i++]
while (j <= right) temp[k++] = arr[j++]
for (x in temp.indices) {
arr[left + x] = temp[x]
}
}
fun main() {
val numbers = intArrayOf(12, 11, 13, 5, 6, 7)
println("Original Array: ${numbers.joinToString()}")
mergeSortInPlace(numbers, 0, numbers.size - 1)
println("Sorted Array: ${numbers.joinToString()}")
}This version doesn’t create new arrays at each division. Instead, it uses index boundaries (left, mid, and right) to manage which part of the array is being processed. This approach is efficient and gives you a deeper understanding of how merging actually works under the hood. For beginners, it’s a good step toward learning memory management in sorting algorithms.
Program 3: Merge Sort for Descending Order
Sometimes we don’t want the smallest element first — we need to sort in descending order. This version modifies the merging condition to arrange numbers from largest to smallest.
fun mergeSortDescending(arr: IntArray): IntArray {
if (arr.size <= 1) return arr
val mid = arr.size / 2
val left = mergeSortDescending(arr.sliceArray(0 until mid))
val right = mergeSortDescending(arr.sliceArray(mid until arr.size))
return mergeDescending(left, right)
}
fun mergeDescending(left: IntArray, right: IntArray): IntArray {
var i = 0
var j = 0
val merged = mutableListOf<Int>()
while (i < left.size && j < right.size) {
if (left[i] >= right[j]) {
merged.add(left[i])
i++
} else {
merged.add(right[j])
j++
}
}
while (i < left.size) merged.add(left[i++])
while (j < right.size) merged.add(right[j++])
return merged.toIntArray()
}
fun main() {
val numbers = intArrayOf(5, 2, 9, 1, 5, 6)
println("Original Array: ${numbers.joinToString()}")
val sortedArray = mergeSortDescending(numbers)
println("Sorted in Descending Order: ${sortedArray.joinToString()}")
}The only difference here is that the comparison in the merge function has been reversed (>= instead of <=). This simple change makes the algorithm sort elements in descending order. It’s a great way for learners to see how small modifications can change the entire output of an algorithm.
Program 4: Merge Sort Using Kotlin Collections
Kotlin offers flexible collection types like List and MutableList, which can make sorting even more readable. This version uses lists instead of arrays for a cleaner, more Kotlin-style approach.
fun mergeSortList(list: List<Int>): List<Int> {
if (list.size <= 1) return list
val middle = list.size / 2
val left = mergeSortList(list.subList(0, middle))
val right = mergeSortList(list.subList(middle, list.size))
return mergeList(left, right)
}
fun mergeList(left: List<Int>, right: List<Int>): List<Int> {
var i = 0
var j = 0
val result = mutableListOf<Int>()
while (i < left.size && j < right.size) {
if (left[i] < right[j]) {
result.add(left[i])
i++
} else {
result.add(right[j])
j++
}
}
while (i < left.size) result.add(left[i++])
while (j < right.size) result.add(right[j++])
return result
}
fun main() {
val numbers = listOf(38, 27, 43, 3, 9, 82, 10)
println("Original List: $numbers")
val sortedList = mergeSortList(numbers)
println("Sorted List: $sortedList")
}This version takes advantage of Kotlin’s collection features to make the code shorter and cleaner. Lists are easier to handle for some developers because they come with built-in methods for slicing and combining. It’s a perfect example of how Kotlin can make even complex algorithms feel elegant and beginner-friendly.
Frequently Asked Questions (FAQ)
Here are some common questions that beginners often ask about Merge Sort in Kotlin.
Q1: What is Merge Sort in Kotlin?
Merge Sort is a sorting algorithm that divides an array into smaller parts, sorts each part, and then merges them back together in the correct order.
Q2: Why is Merge Sort better than Bubble Sort or Insertion Sort?
Merge Sort is faster for large datasets because it has a time complexity of O(n log n), while Bubble Sort and Insertion Sort have O(n²).
Q3: Is Merge Sort a stable algorithm?
Yes, Merge Sort is stable, meaning that elements with equal values maintain their relative order after sorting.
Q4: Can I use Merge Sort for strings or custom objects?
Absolutely. You can modify the comparison condition to compare strings or even object properties, depending on what you want to sort.
Q5: Does Merge Sort use recursion by default?
Yes, Merge Sort is inherently recursive, but it can also be implemented iteratively for advanced use cases.
Conclusion
Merge Sort is one of the most efficient and elegant sorting algorithms you can learn in Kotlin. It breaks problems into smaller, manageable parts and puts them back together in perfect order — a great example of the “divide and conquer” strategy in action. Though the recursive logic may seem challenging at first, once you follow how the array splits and merges, everything falls into place naturally.
By experimenting with the different versions we explored — from the basic recursive version to descending order and list-based approaches — you’ll gain a solid understanding of how Merge Sort works. The more you practice, the more confident you’ll become in handling sorting and algorithm design in Kotlin. So, open your Kotlin IDE, try these examples, and enjoy watching your arrays sort themselves in elegant, efficient style!
