1. Introduction
Sorting is the process of arranging a collection of data elements in a particular order. There are several popular sorting algorithms, but we’ll just focus on merge sort, which is also one of the most efficient sorting algorithms.
In this tutorial, we’ll explore the merge sort algorithm and how to implement it in Kotlin.
2. What Is the Merge Sort Algorithm?
Merge sort is a sorting algorithm that follows the divide-and-conquer principle. The basic idea behind merge sort is to divide the input list or array into two halves, sort each half recursively, and then merge the sorted halves into a single sorted list or array.
Merge sort is a stable sorting algorithm, which means that it maintains the relative order of equal elements in the input list or array. It has a worst-case time complexity of O(n log n), making it one of the most efficient sorting algorithms.
3. How to Implement Merge Sort in Kotlin
The merge sort algorithm can be implemented using a recursive approach. Here’s how it works:
- Divide the array into two halves
- Recursively sort each half
- Merge the two sorted halves into a single sorted array
Now, let’s take a closer look at each step.
3.1. Divide the Array
First, we need to divide the array into two halves by finding the middle index:
middleIndex = (startIndex + endIndex) / 2
In this example, startIndex is the index of the first element in the array, endIndex is the index of the last element in the array, and middleIndex is the index of the middle element.
Once we have the middle index, we can split the array into two halves:
val leftArray = array.sliceArray(startIndex..middleIndex)
val rightArray = array.sliceArray(middleIndex + 1..endIndex)
3.2. Recursively Sort Each Half
Next, we have to recursively sort each half by simply calling the merge sort algorithm on each half of our list or array. This will continue until we have a single element in each half, which is already sorted:
return merge(mergeSort(leftArray), mergeSort(rightArray))
Next, let’s take a deeper dive into the merge() method we use to combine the sorted halves.
3.3. Merge the Two Sorted Halves
Finally, all that is left to do is to merge the two sorted halves into a single sorted array. We just have to compare the first element of each half and add the smaller one to the merged array. We repeat this process until one of the halves is empty, and then we add the remaining elements of the other half to the merged array.
Let’s take a look at the implementation for merging the two sorted arrays:
fun merge(leftArray: IntArray, rightArray: IntArray): IntArray {
val mergedArray = IntArray(leftArray.size + rightArray.size)
var leftIndex = 0
var rightIndex = 0
var mergedIndex = 0
while (leftIndex < leftArray.size && rightIndex < rightArray.size) {
if (leftArray[leftIndex] <= rightArray[rightIndex]) {
mergedArray[mergedIndex] = leftArray[leftIndex]
leftIndex++
} else {
mergedArray[mergedIndex] = rightArray[rightIndex]
rightIndex++
}
mergedIndex++
}
while (leftIndex < leftArray.size) {
mergedArray[mergedIndex] = leftArray[leftIndex]
leftIndex++
mergedIndex++
}
while (rightIndex < rightArray.size) {
mergedArray[mergedIndex] = rightArray[rightIndex]
rightIndex++
mergedIndex++
}
return mergedArray
}
3.4. The Final Result
Let’s combine the code for the two steps above to form the mergeSort method:
fun mergeSort(array: IntArray, startIndex: Int = 0, endIndex: Int = array.size-1): IntArray {
if (array.size <= 1) {
return array
}
val middleIndex = (startIndex + endIndex) / 2
val leftArray = array.sliceArray(startIndex..middleIndex)
val rightArray = array.sliceArray(middleIndex + 1..endIndex)
return merge(mergeSort(leftArray), mergeSort(rightArray))
}
At this point, we’re ready to test our method for correctness:
@Test
fun `sorts an unsorted array`() {
val arr = intArrayOf(5, 3, 9, 7, 1)
val expected = intArrayOf(1, 3, 5, 7, 9)
assertArrayEquals(expected, mergeSort(arr))
}
@Test
fun `sorts a sorted array`() {
val arr = intArrayOf(1, 2, 3, 4, 5)
val expected = intArrayOf(1, 2, 3, 4, 5)
assertArrayEquals(expected, mergeSort(arr))
}
@Test
fun `sorts a reverse sorted array`() {
val arr = intArrayOf(5, 4, 3, 2, 1)
val expected = intArrayOf(1, 2, 3, 4, 5)
assertArrayEquals(expected, mergeSort(arr))
}
4. Challenges of the Merge Sort Algorithm
When it comes to merge sort, developers may face a few challenges when implementing it. One of the main challenges is the additional memory required for the merging process. Merge sort creates temporary arrays during the merging process, which can result in higher memory usage compared to other sorting algorithms.
Another challenge is the recursive nature of the algorithm, which may lead to stack overflow errors if the array is too large. For instance, if we create an array of 10 million elements and call the merge sort algorithm to sort the array, it may result in a stack overflow error.
4.1. Mitigation Strategy
To address these challenges, developers can optimize the merging process by using in-place merging instead of creating temporary arrays. This involves modifying the original array instead of creating new arrays during the merging process. By doing so, developers can reduce memory usage and improve the performance of the algorithm:
fun mergeSortInPlace(arr: IntArray, left: Int = 0, right: Int = arr.size - 1) {
if (left >= right) return
var mid = (left + right) / 2
mergeSortInPlace(arr, left, mid)
mergeSortInPlace(arr, mid + 1, right)
var i = left
var j = mid + 1
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
i++
} else {
val temp = arr[j]
for (k in j downTo i + 1) {
arr[k] = arr[k - 1]
}
arr[i] = temp
i++
mid++
j++
}
}
}
Let’s test our in-place merge sort on a particular scenario that has the potential to trigger a stack overflow error when using the standard merge sort algorithm:
@Test
fun testMergeSortWithLargeArray() {
val unsortedArray = IntArray(100000) { it }.apply{ shuffle() }
mergeSortInPlace(unsortedArray)
val expectedArray = IntArray(100000) { it }
assertContentEquals(unsortedArray, expectedArray)
}
5. Conclusion
In this article, we explored the merge sort algorithm in Kotlin, including how to divide the Array, recursively sort each half, and merge the two sorted halves into a single sorted array. We also investigated some challenges of this algorithm as well as how we can optimize the merging process by using in-place merging instead of creating temporary arrays to address these challenges.
As always, the code samples and relevant test cases pertaining to this article can be found over on GitHub.