1. 引言
排序是将一组数据元素按照特定顺序排列的过程。常见的排序算法有很多，其中归并排序（Merge Sort）是效率较高的一种，也是本文的重点。
在本教程中，我们将深入探讨归并排序算法的原理，并演示如何在 Kotlin 中实现它。
2. 什么是归并排序算法？
归并排序是一种基于分治思想（Divide and Conquer）的经典排序算法。其核心思想是：
✅ 将输入数组一分为二，分别递归地对两部分进行排序，最后将两个有序子数组合并成一个整体有序的数组。
归并排序是一种稳定排序算法，即在排序过程中保持相同元素的相对顺序不变。它的时间复杂度为 *O(n log n)*，适用于大规模数据排序。
3. 如何在 Kotlin 中实现归并排序？
归并排序通常采用递归实现，主要包括三个步骤：
- 分割数组
- 递归排序
- 合并两个有序子数组
下面我们逐一讲解。
3.1. 分割数组
首先，我们需要将数组一分为二，通过计算中间索引实现：
val middleIndex = (startIndex + endIndex) / 2
其中：
startIndex是数组起始索引endIndex是数组结束索引middleIndex是中间索引
接着，将数组分割为两个子数组：
val leftArray = array.sliceArray(startIndex..middleIndex)
val rightArray = array.sliceArray(middleIndex + 1..endIndex)
3.2. 递归排序子数组
接下来，分别对左右两个子数组进行递归排序：
mergeSort(leftArray)
mergeSort(rightArray)
当子数组长度为 1 时，递归终止，因为单个元素本身就是有序的。
最后，将两个有序子数组合并：
return merge(mergeSort(leftArray), mergeSort(rightArray))
3.3. 合并两个有序数组
合并是归并排序的核心操作。其基本思路是：
- 同时遍历两个子数组，比较当前元素，将较小的放入合并结果中
- 当其中一个数组为空时，将另一个数组剩余元素全部追加到结果中
下面是合并函数的实现：
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. 完整的归并排序方法
将以上逻辑整合，形成完整的 mergeSort 方法：
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))
}
3.5. 测试归并排序
我们编写几个测试用例来验证排序逻辑是否正确：
@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. 归并排序的挑战
虽然归并排序效率高，但在实现中也存在一些挑战：
✅ 额外内存开销：归并过程中需要创建临时数组，导致内存占用较高。
✅ 递归深度问题：对于非常大的数组，递归可能导致栈溢出（Stack Overflow）。
例如，对一个包含千万个元素的数组进行排序时，可能会触发栈溢出错误。
4.1. 优化策略：原地归并
为了解决上述问题，可以采用原地归并（In-place Merge）的方式，避免创建临时数组，直接操作原数组。
下面是原地归并排序的实现：
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++
}
}
}
测试一下原地排序是否能处理大数组：
@Test
fun testMergeSortWithLargeArray() {
val unsortedArray = IntArray(100000) { it }.apply { shuffle() }
mergeSortInPlace(unsortedArray)
val expectedArray = IntArray(100000) { it }
assertContentEquals(expectedArray, unsortedArray)
}
⚠️ 注意：原地归并虽然减少了内存开销，但代码更复杂，性能可能略低于标准归并排序，需根据实际场景权衡使用。
5. 总结
在本文中，我们学习了归并排序的基本原理、Kotlin 实现方式，以及其在实际应用中可能遇到的挑战和优化方法。
✅ 优点：时间复杂度稳定（O(n log n)），适合大规模数据排序
✅ 缺点：需要额外空间，递归可能导致栈溢出
✅ 优化方向：使用原地归并减少内存开销
完整代码示例可在 GitHub 上找到。