Merge sort in Kotlin
Sort an array by divide and conquer. Sort each half, then merge the two sorted halves into one sorted array.
- File
MergeSort.kt, 33 lines- Level
- Native tests
- pass in this build
- Toolchain
- Kotlin 2.3 on JDK 25
- Test framework
- JUnit 5
- Run the tests
kotlinc and the JUnit console launcher
// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/merge-sort/. The authors are listed in prov/4MRG7S.jsonl.
/** Sorts a in place, in non-decreasing order. The sort is stable. */
fun <T : Comparable<T>> mergeSort(a: MutableList<T>) {
sort(a, 0, a.size)
}
private fun <T : Comparable<T>> sort(a: MutableList<T>, lo: Int, hi: Int) {
if (hi - lo <= 1) return // @line L1
val mid = lo + (hi - lo) / 2 // @line L2
sort(a, lo, mid) // @line L3
sort(a, mid, hi) // @line L4
merge(a, lo, mid, hi) // @line L5
}
private fun <T : Comparable<T>> merge(a: MutableList<T>, lo: Int, mid: Int, hi: Int) {
val b = a.subList(lo, mid).toList() // @line L6
var i = 0 // @line L7
var j = mid
var k = lo
while (i < b.size && j < hi) { // @line L8
if (b[i] <= a[j]) { // @line L9
a[k] = b[i++]
} else {
a[k] = a[j++] // @line L10
}
k++ // @line L11
}
while (i < b.size) { // @line L12
a[k++] = b[i++] // @line L13
}
}
MergeSortTest.kt 35 lines
// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/merge-sort/. The authors are listed in prov/4MRG7S.jsonl.
import kotlin.random.Random
import org.junit.jupiter.api.Assertions.assertEquals
import org.junit.jupiter.api.Test
class MergeSortTest {
@Test
fun example() {
val a = mutableListOf(38, 27, 43, 3, 9, 82, 10)
mergeSort(a)
assertEquals(listOf(3, 9, 10, 27, 38, 43, 82), a)
}
@Test
fun edges() {
for (a in listOf(listOf(), listOf(1), listOf(2, 1), listOf(1, 1, 1), listOf(3, 2, 1))) {
val b = a.toMutableList()
mergeSort(b)
assertEquals(a.sorted(), b)
}
}
@Test
fun randomAgainstSorted() {
val rng = Random(2150)
repeat(500) {
val a = MutableList(rng.nextInt(61)) { rng.nextInt(101) - 50 }
val want = a.sorted()
mergeSort(a)
assertEquals(want, a)
}
}
}
What the next level needs
- I2 needs the differential and mutation runs (09.5, 09.6), which are M1 work