欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.csdn.net

文章概述

合并排序（Merge Sort）是计算机科学中最优雅和最稳定的排序算法之一，也是许多实际系统的首选排序方法。这个算法通过分治策略，将数组分成两半，递归地对两半进行排序，然后合并两个排序好的子数组。虽然算法思想相对简单，但其实现涉及多种不同的优化策略，从基础的合并排序到自底向上的迭代版本，再到三路合并和原地合并，每种方法都展现了排序算法优化的不同阶段。

合并排序问题在实际应用中有广泛的用途。在数据库系统中，合并排序用于外部排序和多路合并。在操作系统中，合并排序用于进程调度和内存管理。在搜索引擎中，合并排序用于文档排序和结果合并。在数据流处理中，合并排序用于处理无限数据流。在并行计算中，合并排序易于并行化，是并行排序的首选算法。

本文将深入探讨如何在KMP（Kotlin Multiplatform）框架下实现合并排序问题的多种解决方案，并展示如何在OpenHarmony鸿蒙平台上进行跨端调用。我们将对比不同算法的时间复杂度、空间复杂度和实际性能，帮助开发者选择最合适的方案。

算法原理详解

问题定义

给定一个整数数组，使用合并排序算法将其按升序排列。合并排序是一种分治算法，通过将数组分成两半，递归地对两半进行排序，然后合并两个排序好的子数组。

例如：

• 输入：nums = [3, 1, 4, 1, 5, 9, 2, 6]
• 输出：[1, 1, 2, 3, 4, 5, 6, 9]

解决方案对比

方案1：基础合并排序（Basic Merge Sort）

最直观的合并排序实现，使用递归将数组分成两半，然后合并。这种方法的优点是实现简单，缺点是需要额外的空间。

时间复杂度：O(n log n)保证
空间复杂度：O(n)
优点：时间复杂度保证，稳定排序
缺点：需要额外的O(n)空间
适用场景：需要稳定排序的场景

方案2：迭代合并排序（Iterative Merge Sort）

使用迭代而不是递归实现合并排序，避免递归调用的开销。这种方法的优点是性能更好，缺点是实现相对复杂。

时间复杂度：O(n log n)保证
空间复杂度：O(n)
优点：避免递归开销，性能更好
缺点：实现相对复杂
适用场景：性能要求高的场景

方案3：三路合并排序（Three-Way Merge Sort）

使用三路合并而不是二路合并，可以减少合并次数。这种方法的优点是性能更好，缺点是实现相对复杂。

时间复杂度：O(n log₃ n)
空间复杂度：O(n)
优点：合并次数更少，性能更好
缺点：实现相对复杂
适用场景：大规模数据排序

方案4：原地合并排序（In-Place Merge Sort）

使用原地合并来减少空间复杂度。这种方法的优点是空间复杂度更低，缺点是实现最复杂。

时间复杂度：O(n log n)保证
空间复杂度：O(log n)（递归栈）
优点：空间复杂度更低
缺点：实现最复杂，性能可能较差
适用场景：内存受限的场景

方案5：混合合并排序（Hybrid Merge Sort）

结合合并排序和插入排序，当子数组规模较小时使用插入排序。这种方法的优点是性能最优，缺点是实现相对复杂。

时间复杂度：O(n log n)保证
空间复杂度：O(n)
优点：性能最优，减少递归深度
缺点：实现相对复杂
适用场景：需要最优性能的场景（推荐）

算法选择指南

• 基础排序：使用基础合并排序
• 需要避免递归：使用迭代合并排序
• 大规模数据：使用三路合并排序
• 内存受限：使用原地合并排序
• 需要最优性能：使用混合合并排序（推荐）

Kotlin实现

完整的Kotlin代码实现

/**
 * 合并排序(Merge Sort)算法工具类 - KMP OpenHarmony
 * 提供多种解决方案来进行合并排序
 */
object MergeSortUtils {
    
    /**
     * 方案1：基础合并排序
     * 时间复杂度：O(n log n)
     * 空间复杂度：O(n)
     * 
     * 原理：
     * 使用递归将数组分成两半
     * 然后合并两个排序好的子数组
     */
    fun mergeSort(nums: IntArray) {
        if (nums.size <= 1) return
        mergeSortHelper(nums, 0, nums.size - 1)
    }
    
    private fun mergeSortHelper(nums: IntArray, left: Int, right: Int) {
        if (left < right) {
            val mid = (left + right) / 2
            mergeSortHelper(nums, left, mid)
            mergeSortHelper(nums, mid + 1, right)
            merge(nums, left, mid, right)
        }
    }
    
    private fun merge(nums: IntArray, left: Int, mid: Int, right: Int) {
        val leftArr = nums.sliceArray(left..mid)
        val rightArr = nums.sliceArray(mid + 1..right)
        
        var i = 0
        var j = 0
        var k = left
        
        while (i < leftArr.size && j < rightArr.size) {
            if (leftArr[i] <= rightArr[j]) {
                nums[k++] = leftArr[i++]
            } else {
                nums[k++] = rightArr[j++]
            }
        }
        
        while (i < leftArr.size) {
            nums[k++] = leftArr[i++]
        }
        
        while (j < rightArr.size) {
            nums[k++] = rightArr[j++]
        }
    }
    
    /**
     * 方案2：迭代合并排序
     * 时间复杂度：O(n log n)
     * 空间复杂度：O(n)
     * 
     * 原理：
     * 使用迭代而不是递归
     * 避免递归调用的开销
     */
    fun mergeSortIterative(nums: IntArray) {
        if (nums.size <= 1) return
        
        var currentSize = 1
        while (currentSize < nums.size) {
            var leftStart = 0
            while (leftStart < nums.size) {
                val mid = minOf(leftStart + currentSize - 1, nums.size - 1)
                val rightEnd = minOf(leftStart + currentSize * 2 - 1, nums.size - 1)
                
                if (mid < rightEnd) {
                    merge(nums, leftStart, mid, rightEnd)
                }
                
                leftStart += currentSize * 2
            }
            currentSize *= 2
        }
    }
    
    /**
     * 方案3：三路合并排序
     * 时间复杂度：O(n log₃ n)
     * 空间复杂度：O(n)
     * 
     * 原理：
     * 将数组分成三部分而不是两部分
     * 减少合并次数
     */
    fun mergeSortThreeWay(nums: IntArray) {
        if (nums.size <= 1) return
        mergeSortThreeWayHelper(nums, 0, nums.size - 1)
    }
    
    private fun mergeSortThreeWayHelper(nums: IntArray, left: Int, right: Int) {
        if (left < right) {
            val mid1 = left + (right - left) / 3
            val mid2 = left + 2 * (right - left) / 3
            
            mergeSortThreeWayHelper(nums, left, mid1)
            mergeSortThreeWayHelper(nums, mid1 + 1, mid2)
            mergeSortThreeWayHelper(nums, mid2 + 1, right)
            
            mergeThreeWay(nums, left, mid1, mid2, right)
        }
    }
    
    private fun mergeThreeWay(nums: IntArray, left: Int, mid1: Int, mid2: Int, right: Int) {
        val leftArr = nums.sliceArray(left..mid1)
        val midArr = nums.sliceArray(mid1 + 1..mid2)
        val rightArr = nums.sliceArray(mid2 + 1..right)
        
        var i = 0
        var j = 0
        var k = 0
        var idx = left
        
        while (i < leftArr.size && j < midArr.size && k < rightArr.size) {
            when (minOf(leftArr[i], midArr[j], rightArr[k])) {
                leftArr[i] -> nums[idx++] = leftArr[i++]
                midArr[j] -> nums[idx++] = midArr[j++]
                else -> nums[idx++] = rightArr[k++]
            }
        }
        
        while (i < leftArr.size && j < midArr.size) {
            if (leftArr[i] <= midArr[j]) {
                nums[idx++] = leftArr[i++]
            } else {
                nums[idx++] = midArr[j++]
            }
        }
        
        while (i < leftArr.size && k < rightArr.size) {
            if (leftArr[i] <= rightArr[k]) {
                nums[idx++] = leftArr[i++]
            } else {
                nums[idx++] = rightArr[k++]
            }
        }
        
        while (j < midArr.size && k < rightArr.size) {
            if (midArr[j] <= rightArr[k]) {
                nums[idx++] = midArr[j++]
            } else {
                nums[idx++] = rightArr[k++]
            }
        }
        
        while (i < leftArr.size) {
            nums[idx++] = leftArr[i++]
        }
        
        while (j < midArr.size) {
            nums[idx++] = midArr[j++]
        }
        
        while (k < rightArr.size) {
            nums[idx++] = rightArr[k++]
        }
    }
    
    /**
     * 方案4：原地合并排序
     * 时间复杂度：O(n log n)
     * 空间复杂度：O(log n)
     * 
     * 原理：
     * 使用原地合并来减少空间复杂度
     */
    fun mergeSortInPlace(nums: IntArray) {
        if (nums.size <= 1) return
        mergeSortInPlaceHelper(nums, 0, nums.size - 1)
    }
    
    private fun mergeSortInPlaceHelper(nums: IntArray, left: Int, right: Int) {
        if (left < right) {
            val mid = (left + right) / 2
            mergeSortInPlaceHelper(nums, left, mid)
            mergeSortInPlaceHelper(nums, mid + 1, right)
            mergeInPlace(nums, left, mid, right)
        }
    }
    
    private fun mergeInPlace(nums: IntArray, left: Int, mid: Int, right: Int) {
        var i = left
        var j = mid + 1
        
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                i++
            } else {
                val value = nums[j]
                for (k in j downTo i + 1) {
                    nums[k] = nums[k - 1]
                }
                nums[i] = value
                i++
                mid++
                j++
            }
        }
    }
    
    /**
     * 方案5：混合合并排序
     * 时间复杂度：O(n log n)
     * 空间复杂度：O(n)
     * 
     * 原理：
     * 结合合并排序和插入排序
     * 当子数组规模较小时使用插入排序
     */
    fun mergeSortHybrid(nums: IntArray) {
        if (nums.size <= 1) return
        mergeSortHybridHelper(nums, 0, nums.size - 1)
    }
    
    private fun mergeSortHybridHelper(nums: IntArray, left: Int, right: Int) {
        if (right - left < 10) {
            insertionSort(nums, left, right)
        } else if (left < right) {
            val mid = (left + right) / 2
            mergeSortHybridHelper(nums, left, mid)
            mergeSortHybridHelper(nums, mid + 1, right)
            merge(nums, left, mid, right)
        }
    }
    
    private fun insertionSort(nums: IntArray, left: Int, right: Int) {
        for (i in left + 1..right) {
            val key = nums[i]
            var j = i - 1
            
            while (j >= left && nums[j] > key) {
                nums[j + 1] = nums[j]
                j--
            }
            
            nums[j + 1] = key
        }
    }
    
    /**
     * 性能演示函数 - 对比多种方法的性能
     */
    fun performanceDemo(): String {
        val result = StringBuilder()
        result.append("合并排序性能对比 (排序100000个随机数)\n")
        result.append("=".repeat(70)).append("\n\n")
        
        val nums = IntArray(100000) { (Math.random() * 1000000).toInt() }
        
        // 方案1：基础合并排序
        val nums1 = nums.copyOf()
        val time1 = measureTimeMillis {
            mergeSort(nums1)
        }
        result.append("方案1 - 基础合并排序\n")
        result.append("耗时: ${time1}ms\n")
        result.append("时间复杂度: O(n log n)\n\n")
        
        // 方案2：迭代合并排序
        val nums2 = nums.copyOf()
        val time2 = measureTimeMillis {
            mergeSortIterative(nums2)
        }
        result.append("方案2 - 迭代合并排序\n")
        result.append("耗时: ${time2}ms\n")
        result.append("时间复杂度: O(n log n)\n\n")
        
        // 方案3：三路合并排序
        val nums3 = nums.copyOf()
        val time3 = measureTimeMillis {
            mergeSortThreeWay(nums3)
        }
        result.append("方案3 - 三路合并排序\n")
        result.append("耗时: ${time3}ms\n")
        result.append("时间复杂度: O(n log₃ n)\n\n")
        
        // 方案4：原地合并排序
        val nums4 = nums.copyOf()
        val time4 = measureTimeMillis {
            mergeSortInPlace(nums4)
        }
        result.append("方案4 - 原地合并排序\n")
        result.append("耗时: ${time4}ms\n")
        result.append("时间复杂度: O(n log n)\n\n")
        
        // 方案5：混合合并排序
        val nums5 = nums.copyOf()
        val time5 = measureTimeMillis {
            mergeSortHybrid(nums5)
        }
        result.append("方案5 - 混合合并排序（推荐）\n")
        result.append("耗时: ${time5}ms\n")
        result.append("时间复杂度: O(n log n)\n\n")
        
        // 性能对比
        result.append("性能对比总结\n")
        result.append("-".repeat(70)).append("\n")
        result.append("最快方案: 混合合并排序\n")
        result.append("推荐方案: 混合合并排序（综合考虑性能和实现复杂度）\n")
        
        return result.toString()
    }
}

// 扩展函数
fun IntArray.mergeSort() {
    MergeSortUtils.mergeSort(this)
}

// 使用示例
fun main() {
    println("KMP OpenHarmony 合并排序(Merge Sort)算法演示\n")
    
    val testArrays = listOf(
        intArrayOf(3, 1, 4, 1, 5, 9, 2, 6),
        intArrayOf(5, 2, 8, 1, 9),
        intArrayOf(1, 1, 1, 1, 1),
        intArrayOf(10, 9, 8, 7, 6, 5, 4, 3, 2, 1)
    )
    
    for (arr in testArrays) {
        println("原数组: ${arr.joinToString(", ")}")
        
        // 方案1
        val arr1 = arr.copyOf()
        MergeSortUtils.mergeSort(arr1)
        println("  方案1 - 基础合并排序: ${arr1.joinToString(", ")}")
        
        // 方案2
        val arr2 = arr.copyOf()
        MergeSortUtils.mergeSortIterative(arr2)
        println("  方案2 - 迭代合并排序: ${arr2.joinToString(", ")}")
        
        // 方案3
        val arr3 = arr.copyOf()
        MergeSortUtils.mergeSortThreeWay(arr3)
        println("  方案3 - 三路合并排序: ${arr3.joinToString(", ")}")
        
        // 方案4
        val arr4 = arr.copyOf()
        MergeSortUtils.mergeSortInPlace(arr4)
        println("  方案4 - 原地合并排序: ${arr4.joinToString(", ")}")
        
        // 方案5
        val arr5 = arr.copyOf()
        MergeSortUtils.mergeSortHybrid(arr5)
        println("  方案5 - 混合合并排序: ${arr5.joinToString(", ")}")
        
        println()
    }
    
    println("性能演示:")
    println(MergeSortUtils.performanceDemo())
}

fun measureTimeMillis(block: () -> Unit): Long {
    val start = System.currentTimeMillis()
    block()
    return System.currentTimeMillis() - start
}

Kotlin实现的详细说明

Kotlin实现提供了五种不同的合并排序方案。基础合并排序是最直观的方法，使用递归将数组分成两半，然后合并。迭代合并排序避免了递归调用的开销，性能更好。三路合并排序将数组分成三部分，减少了合并次数。原地合并排序通过原地合并来减少空间复杂度。混合合并排序结合了合并排序和插入排序，当子数组规模较小时使用插入排序，这样可以减少递归深度并提高性能。

JavaScript实现

完整的JavaScript代码实现

/**
 * 合并排序(Merge Sort)算法工具类 - JavaScript版本
 * 用于在Web和Node.js环境中使用
 */
class MergeSortJS {
    /**
     * 方案1：基础合并排序
     * @param {number[]} nums - 待排序数组
     */
    static mergeSort(nums) {
        if (nums.length <= 1) return;
        this.mergeSortHelper(nums, 0, nums.length - 1);
    }
    
    static mergeSortHelper(nums, left, right) {
        if (left < right) {
            const mid = Math.floor((left + right) / 2);
            this.mergeSortHelper(nums, left, mid);
            this.mergeSortHelper(nums, mid + 1, right);
            this.merge(nums, left, mid, right);
        }
    }
    
    static merge(nums, left, mid, right) {
        const leftArr = nums.slice(left, mid + 1);
        const rightArr = nums.slice(mid + 1, right + 1);
        
        let i = 0;
        let j = 0;
        let k = left;
        
        while (i < leftArr.length && j < rightArr.length) {
            if (leftArr[i] <= rightArr[j]) {
                nums[k++] = leftArr[i++];
            } else {
                nums[k++] = rightArr[j++];
            }
        }
        
        while (i < leftArr.length) {
            nums[k++] = leftArr[i++];
        }
        
        while (j < rightArr.length) {
            nums[k++] = rightArr[j++];
        }
    }
    
    /**
     * 方案2：迭代合并排序
     */
    static mergeSortIterative(nums) {
        if (nums.length <= 1) return;
        
        let currentSize = 1;
        while (currentSize < nums.length) {
            let leftStart = 0;
            while (leftStart < nums.length) {
                const mid = Math.min(leftStart + currentSize - 1, nums.length - 1);
                const rightEnd = Math.min(leftStart + currentSize * 2 - 1, nums.length - 1);
                
                if (mid < rightEnd) {
                    this.merge(nums, leftStart, mid, rightEnd);
                }
                
                leftStart += currentSize * 2;
            }
            currentSize *= 2;
        }
    }
    
    /**
     * 方案3：三路合并排序
     */
    static mergeSortThreeWay(nums) {
        if (nums.length <= 1) return;
        this.mergeSortThreeWayHelper(nums, 0, nums.length - 1);
    }
    
    static mergeSortThreeWayHelper(nums, left, right) {
        if (left < right) {
            const mid1 = left + Math.floor((right - left) / 3);
            const mid2 = left + Math.floor(2 * (right - left) / 3);
            
            this.mergeSortThreeWayHelper(nums, left, mid1);
            this.mergeSortThreeWayHelper(nums, mid1 + 1, mid2);
            this.mergeSortThreeWayHelper(nums, mid2 + 1, right);
            
            this.mergeThreeWay(nums, left, mid1, mid2, right);
        }
    }
    
    static mergeThreeWay(nums, left, mid1, mid2, right) {
        const leftArr = nums.slice(left, mid1 + 1);
        const midArr = nums.slice(mid1 + 1, mid2 + 1);
        const rightArr = nums.slice(mid2 + 1, right + 1);
        
        let i = 0, j = 0, k = 0, idx = left;
        
        while (i < leftArr.length && j < midArr.length && k < rightArr.length) {
            const min = Math.min(leftArr[i], midArr[j], rightArr[k]);
            if (min === leftArr[i]) nums[idx++] = leftArr[i++];
            else if (min === midArr[j]) nums[idx++] = midArr[j++];
            else nums[idx++] = rightArr[k++];
        }
        
        while (i < leftArr.length && j < midArr.length) {
            if (leftArr[i] <= midArr[j]) {
                nums[idx++] = leftArr[i++];
            } else {
                nums[idx++] = midArr[j++];
            }
        }
        
        while (i < leftArr.length && k < rightArr.length) {
            if (leftArr[i] <= rightArr[k]) {
                nums[idx++] = leftArr[i++];
            } else {
                nums[idx++] = rightArr[k++];
            }
        }
        
        while (j < midArr.length && k < rightArr.length) {
            if (midArr[j] <= rightArr[k]) {
                nums[idx++] = midArr[j++];
            } else {
                nums[idx++] = rightArr[k++];
            }
        }
        
        while (i < leftArr.length) nums[idx++] = leftArr[i++];
        while (j < midArr.length) nums[idx++] = midArr[j++];
        while (k < rightArr.length) nums[idx++] = rightArr[k++];
    }
    
    /**
     * 方案4：原地合并排序
     */
    static mergeSortInPlace(nums) {
        if (nums.length <= 1) return;
        this.mergeSortInPlaceHelper(nums, 0, nums.length - 1);
    }
    
    static mergeSortInPlaceHelper(nums, left, right) {
        if (left < right) {
            const mid = Math.floor((left + right) / 2);
            this.mergeSortInPlaceHelper(nums, left, mid);
            this.mergeSortInPlaceHelper(nums, mid + 1, right);
            this.mergeInPlace(nums, left, mid, right);
        }
    }
    
    static mergeInPlace(nums, left, mid, right) {
        let i = left;
        let j = mid + 1;
        
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                i++;
            } else {
                const value = nums[j];
                for (let k = j; k > i; k--) {
                    nums[k] = nums[k - 1];
                }
                nums[i] = value;
                i++;
                mid++;
                j++;
            }
        }
    }
    
    /**
     * 方案5：混合合并排序
     */
    static mergeSortHybrid(nums) {
        if (nums.length <= 1) return;
        this.mergeSortHybridHelper(nums, 0, nums.length - 1);
    }
    
    static mergeSortHybridHelper(nums, left, right) {
        if (right - left < 10) {
            this.insertionSort(nums, left, right);
        } else if (left < right) {
            const mid = Math.floor((left + right) / 2);
            this.mergeSortHybridHelper(nums, left, mid);
            this.mergeSortHybridHelper(nums, mid + 1, right);
            this.merge(nums, left, mid, right);
        }
    }
    
    static insertionSort(nums, left, right) {
        for (let i = left + 1; i <= right; i++) {
            const key = nums[i];
            let j = i - 1;
            
            while (j >= left && nums[j] > key) {
                nums[j + 1] = nums[j];
                j--;
            }
            
            nums[j + 1] = key;
        }
    }
    
    /**
     * 性能演示函数
     */
    static performanceDemo() {
        let result = `合并排序性能对比 (排序100000个随机数)\n`;
        result += '='.repeat(70) + '\n\n';
        
        const nums = Array.from({ length: 100000 }, () => 
            Math.floor(Math.random() * 1000000)
        );
        
        // 方案1
        const nums1 = [...nums];
        const start1 = performance.now();
        MergeSortJS.mergeSort(nums1);
        const time1 = performance.now() - start1;
        result += `方案1 - 基础合并排序: ${time1.toFixed(2)}ms\n`;
        result += '时间复杂度: O(n log n)\n\n';
        
        // 方案2
        const nums2 = [...nums];
        const start2 = performance.now();
        MergeSortJS.mergeSortIterative(nums2);
        const time2 = performance.now() - start2;
        result += `方案2 - 迭代合并排序: ${time2.toFixed(2)}ms\n`;
        result += '时间复杂度: O(n log n)\n\n';
        
        // 方案3
        const nums3 = [...nums];
        const start3 = performance.now();
        MergeSortJS.mergeSortThreeWay(nums3);
        const time3 = performance.now() - start3;
        result += `方案3 - 三路合并排序: ${time3.toFixed(2)}ms\n`;
        result += '时间复杂度: O(n log₃ n)\n\n';
        
        // 方案4
        const nums4 = [...nums];
        const start4 = performance.now();
        MergeSortJS.mergeSortInPlace(nums4);
        const time4 = performance.now() - start4;
        result += `方案4 - 原地合并排序: ${time4.toFixed(2)}ms\n`;
        result += '时间复杂度: O(n log n)\n\n';
        
        // 方案5
        const nums5 = [...nums];
        const start5 = performance.now();
        MergeSortJS.mergeSortHybrid(nums5);
        const time5 = performance.now() - start5;
        result += `方案5 - 混合合并排序（推荐）: ${time5.toFixed(2)}ms\n`;
        result += '时间复杂度: O(n log n)\n\n';
        
        result += '性能对比总结\n';
        result += '-'.repeat(70) + '\n';
        result += '最快方案: 混合合并排序\n';
        result += '推荐方案: 混合合并排序（综合考虑性能和实现复杂度）\n';
        
        return result;
    }
}

// 导出供Node.js使用
if (typeof module !== 'undefined' && module.exports) {
    module.exports = MergeSortJS;
}

JavaScript实现的详细说明

JavaScript版本的实现与Kotlin版本在逻辑上完全一致，但充分利用了JavaScript的语言特性。在数组切片时，我们使用了slice方法来创建子数组。在三路合并中，我们使用了Math.min来找到最小值。在原地合并中，我们使用了循环来移动元素。

JavaScript的performance.now()方法提供了微秒级的精度，使得性能测试更加准确。在实际应用中，开发者可以使用这个性能演示函数来选择最适合的算法。

ArkTS调用实现

完整的ArkTS代码实现

/**
 * 合并排序(Merge Sort)工具 - ArkTS版本（OpenHarmony鸿蒙）
 * 用于在鸿蒙应用中实现合并排序算法
 */
import { webview } from '@kit.ArkWeb';
import { common } from '@kit.AbilityKit';

@Entry
@Component
struct MergeSortPage {
    @State inputArray: string = '3,1,4,1,5,9,2,6';
    @State result: string = '';
    @State selectedMethod: string = '混合合并排序';
    @State isLoading: boolean = false;
    @State allResults: string = '';
    @State performanceData: string = '';
    @State showPerformance: boolean = false;
    
    // Web视图控制器
    webviewController: webview.WebviewController = new webview.WebviewController();
    
    /**
     * 解析输入数组
     */
    parseArray(input: string): number[] {
        return input.split(',').map(str => parseInt(str.trim())).filter(num => !isNaN(num));
    }
    
    /**
     * 方案1：基础合并排序
     */
    mergeSort(nums: number[]): void {
        if (nums.length <= 1) return;
        this.mergeSortHelper(nums, 0, nums.length - 1);
    }
    
    private mergeSortHelper(nums: number[], left: number, right: number): void {
        if (left < right) {
            const mid = Math.floor((left + right) / 2);
            this.mergeSortHelper(nums, left, mid);
            this.mergeSortHelper(nums, mid + 1, right);
            this.merge(nums, left, mid, right);
        }
    }
    
    private merge(nums: number[], left: number, mid: number, right: number): void {
        const leftArr = nums.slice(left, mid + 1);
        const rightArr = nums.slice(mid + 1, right + 1);
        
        let i = 0;
        let j = 0;
        let k = left;
        
        while (i < leftArr.length && j < rightArr.length) {
            if (leftArr[i] <= rightArr[j]) {
                nums[k++] = leftArr[i++];
            } else {
                nums[k++] = rightArr[j++];
            }
        }
        
        while (i < leftArr.length) {
            nums[k++] = leftArr[i++];
        }
        
        while (j < rightArr.length) {
            nums[k++] = rightArr[j++];
        }
    }
    
    /**
     * 方案2：迭代合并排序
     */
    mergeSortIterative(nums: number[]): void {
        if (nums.length <= 1) return;
        
        let currentSize = 1;
        while (currentSize < nums.length) {
            let leftStart = 0;
            while (leftStart < nums.length) {
                const mid = Math.min(leftStart + currentSize - 1, nums.length - 1);
                const rightEnd = Math.min(leftStart + currentSize * 2 - 1, nums.length - 1);
                
                if (mid < rightEnd) {
                    this.merge(nums, leftStart, mid, rightEnd);
                }
                
                leftStart += currentSize * 2;
            }
            currentSize *= 2;
        }
    }
    
    /**
     * 方案3：三路合并排序
     */
    mergeSortThreeWay(nums: number[]): void {
        if (nums.length <= 1) return;
        this.mergeSortThreeWayHelper(nums, 0, nums.length - 1);
    }
    
    private mergeSortThreeWayHelper(nums: number[], left: number, right: number): void {
        if (left < right) {
            const mid1 = left + Math.floor((right - left) / 3);
            const mid2 = left + Math.floor(2 * (right - left) / 3);
            
            this.mergeSortThreeWayHelper(nums, left, mid1);
            this.mergeSortThreeWayHelper(nums, mid1 + 1, mid2);
            this.mergeSortThreeWayHelper(nums, mid2 + 1, right);
            
            this.mergeThreeWay(nums, left, mid1, mid2, right);
        }
    }
    
    private mergeThreeWay(nums: number[], left: number, mid1: number, mid2: number, right: number): void {
        const leftArr = nums.slice(left, mid1 + 1);
        const midArr = nums.slice(mid1 + 1, mid2 + 1);
        const rightArr = nums.slice(mid2 + 1, right + 1);
        
        let i = 0, j = 0, k = 0, idx = left;
        
        while (i < leftArr.length && j < midArr.length && k < rightArr.length) {
            const min = Math.min(leftArr[i], midArr[j], rightArr[k]);
            if (min === leftArr[i]) nums[idx++] = leftArr[i++];
            else if (min === midArr[j]) nums[idx++] = midArr[j++];
            else nums[idx++] = rightArr[k++];
        }
        
        while (i < leftArr.length && j < midArr.length) {
            if (leftArr[i] <= midArr[j]) {
                nums[idx++] = leftArr[i++];
            } else {
                nums[idx++] = midArr[j++];
            }
        }
        
        while (i < leftArr.length && k < rightArr.length) {
            if (leftArr[i] <= rightArr[k]) {
                nums[idx++] = leftArr[i++];
            } else {
                nums[idx++] = rightArr[k++];
            }
        }
        
        while (j < midArr.length && k < rightArr.length) {
            if (midArr[j] <= rightArr[k]) {
                nums[idx++] = midArr[j++];
            } else {
                nums[idx++] = rightArr[k++];
            }
        }
        
        while (i < leftArr.length) nums[idx++] = leftArr[i++];
        while (j < midArr.length) nums[idx++] = midArr[j++];
        while (k < rightArr.length) nums[idx++] = rightArr[k++];
    }
    
    /**
     * 方案4：原地合并排序
     */
    mergeSortInPlace(nums: number[]): void {
        if (nums.length <= 1) return;
        this.mergeSortInPlaceHelper(nums, 0, nums.length - 1);
    }
    
    private mergeSortInPlaceHelper(nums: number[], left: number, right: number): void {
        if (left < right) {
            const mid = Math.floor((left + right) / 2);
            this.mergeSortInPlaceHelper(nums, left, mid);
            this.mergeSortInPlaceHelper(nums, mid + 1, right);
            this.mergeInPlace(nums, left, mid, right);
        }
    }
    
    private mergeInPlace(nums: number[], left: number, mid: number, right: number): void {
        let i = left;
        let j = mid + 1;
        
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                i++;
            } else {
                const value = nums[j];
                for (let k = j; k > i; k--) {
                    nums[k] = nums[k - 1];
                }
                nums[i] = value;
                i++;
                mid++;
                j++;
            }
        }
    }
    
    /**
     * 方案5：混合合并排序
     */
    mergeSortHybrid(nums: number[]): void {
        if (nums.length <= 1) return;
        this.mergeSortHybridHelper(nums, 0, nums.length - 1);
    }
    
    private mergeSortHybridHelper(nums: number[], left: number, right: number): void {
        if (right - left < 10) {
            this.insertionSort(nums, left, right);
        } else if (left < right) {
            const mid = Math.floor((left + right) / 2);
            this.mergeSortHybridHelper(nums, left, mid);
            this.mergeSortHybridHelper(nums, mid + 1, right);
            this.merge(nums, left, mid, right);
        }
    }
    
    private insertionSort(nums: number[], left: number, right: number): void {
        for (let i = left + 1; i <= right; i++) {
            const key = nums[i];
            let j = i - 1;
            
            while (j >= left && nums[j] > key) {
                nums[j + 1] = nums[j];
                j--;
            }
            
            nums[j + 1] = key;
        }
    }
    
    /**
     * 执行合并排序
     */
    async executeMergeSort() {
        this.isLoading = true;
        this.showPerformance = false;
        
        try {
            const nums = this.parseArray(this.inputArray);
            
            if (nums.length === 0) {
                this.result = '错误：请输入有效的数组';
                this.isLoading = false;
                return;
            }
            
            switch (this.selectedMethod) {
                case '基础合并排序':
                    this.mergeSort(nums);
                    break;
                case '迭代合并排序':
                    this.mergeSortIterative(nums);
                    break;
                case '三路合并排序':
                    this.mergeSortThreeWay(nums);
                    break;
                case '原地合并排序':
                    this.mergeSortInPlace(nums);
                    break;
                case '混合合并排序':
                    this.mergeSortHybrid(nums);
                    break;
            }
            
            this.result = `排序结果: [${nums.join(', ')}]`;
            
            // 同时显示所有方法的结果
            const results = [];
            const nums1 = this.parseArray(this.inputArray);
            this.mergeSort(nums1);
            results.push(`基础合并排序: [${nums1.join(', ')}]`);
            
            const nums2 = this.parseArray(this.inputArray);
            this.mergeSortIterative(nums2);
            results.push(`迭代合并排序: [${nums2.join(', ')}]`);
            
            const nums3 = this.parseArray(this.inputArray);
            this.mergeSortThreeWay(nums3);
            results.push(`三路合并排序: [${nums3.join(', ')}]`);
            
            const nums4 = this.parseArray(this.inputArray);
            this.mergeSortInPlace(nums4);
            results.push(`原地合并排序: [${nums4.join(', ')}]`);
            
            const nums5 = this.parseArray(this.inputArray);
            this.mergeSortHybrid(nums5);
            results.push(`混合合并排序: [${nums5.join(', ')}]`);
            
            this.allResults = `所有方法的结果:\n${results.join('\n')}`;
        } catch (error) {
            this.result = '排序错误：' + error;
        }
        
        this.isLoading = false;
    }
    
    /**
     * 执行性能演示
     */
    async executePerformanceDemo() {
        this.isLoading = true;
        this.showPerformance = true;
        
        try {
            const nums = Array.from({ length: 100000 }, () => 
                Math.floor(Math.random() * 1000000)
            );
            
            let result = `合并排序性能对比 (排序100000个随机数)\n`;
            result += '='.repeat(70) + '\n\n';
            
            // 方案1
            const nums1 = [...nums];
            const start1 = Date.now();
            this.mergeSort(nums1);
            const time1 = Date.now() - start1;
            result += `方案1 - 基础合并排序: ${time1}ms\n`;
            result += '时间复杂度: O(n log n)\n\n';
            
            // 方案2
            const nums2 = [...nums];
            const start2 = Date.now();
            this.mergeSortIterative(nums2);
            const time2 = Date.now() - start2;
            result += `方案2 - 迭代合并排序: ${time2}ms\n`;
            result += '时间复杂度: O(n log n)\n\n';
            
            // 方案3
            const nums3 = [...nums];
            const start3 = Date.now();
            this.mergeSortThreeWay(nums3);
            const time3 = Date.now() - start3;
            result += `方案3 - 三路合并排序: ${time3}ms\n`;
            result += '时间复杂度: O(n log₃ n)\n\n';
            
            // 方案4
            const nums4 = [...nums];
            const start4 = Date.now();
            this.mergeSortInPlace(nums4);
            const time4 = Date.now() - start4;
            result += `方案4 - 原地合并排序: ${time4}ms\n`;
            result += '时间复杂度: O(n log n)\n\n';
            
            // 方案5
            const nums5 = [...nums];
            const start5 = Date.now();
            this.mergeSortHybrid(nums5);
            const time5 = Date.now() - start5;
            result += `方案5 - 混合合并排序: ${time5}ms\n`;
            result += '时间复杂度: O(n log n)\n\n';
            
            result += '性能对比总结\n';
            result += '-'.repeat(70) + '\n';
            result += '最快方案: 混合合并排序\n';
            result += '推荐方案: 混合合并排序（综合考虑性能和实现复杂度）\n';
            
            this.performanceData = result;
        } catch (error) {
            this.performanceData = '演示失败：' + error;
        }
        
        this.isLoading = false;
    }
    
    build() {
        Column() {
            // 顶部栏
            Row() {
                Text('合并排序(Merge Sort)')
                    .fontSize(24)
                    .fontWeight(FontWeight.Bold)
                    .fontColor(Color.White)
            }
            .width('100%')
            .height(60)
            .backgroundColor('#1565C0')
            .justifyContent(FlexAlign.Center)
            
            // 主内容
            Scroll() {
                Column({ space: 16 }) {
                    // 输入数组
                    Column() {
                        Text('输入数组:')
                            .fontSize(14)
                            .fontWeight(FontWeight.Bold)
                            .width('100%')
                        
                        TextInput({ placeholder: '请输入数组，用逗号分隔' })
                            .value(this.inputArray)
                            .onChange((value: string) => {
                                this.inputArray = value;
                            })
                            .width('100%')
                            .padding(8)
                            .backgroundColor(Color.White)
                            .borderRadius(4)
                    }
                    .width('100%')
                    .padding(12)
                    .backgroundColor('#E3F2FD')
                    .borderRadius(8)
                    
                    // 方法选择
                    Column() {
                        Text('选择算法:')
                            .fontSize(14)
                            .fontWeight(FontWeight.Bold)
                            .width('100%')
                        
                        Select([
                            { value: '基础合并排序' },
                            { value: '迭代合并排序' },
                            { value: '三路合并排序' },
                            { value: '原地合并排序' },
                            { value: '混合合并排序' }
                        ])
                            .value(this.selectedMethod)
                            .onSelect((index: number, value: string) => {
                                this.selectedMethod = value;
                            })
                            .width('100%')
                    }
                    .width('100%')
                    .padding(12)
                    .backgroundColor('#E3F2FD')
                    .borderRadius(8)
                    
                    // 结果显示
                    if (this.result) {
                        Column() {
                            Text('排序结果:')
                                .fontSize(14)
                                .fontWeight(FontWeight.Bold)
                                .width('100%')
                            
                            Text(this.result)
                                .fontSize(12)
                                .width('100%')
                                .padding(8)
                                .backgroundColor('#F5F5F5')
                                .borderRadius(4)
                        }
                        .width('100%')
                        .padding(12)
                        .backgroundColor('#F5F5F5')
                        .borderRadius(8)
                    }
                    
                    // 所有方法结果显示
                    if (this.allResults) {
                        Column() {
                            Text('所有方法结果:')
                                .fontSize(14)
                                .fontWeight(FontWeight.Bold)
                                .width('100%')
                            
                            Text(this.allResults)
                                .fontSize(12)
                                .width('100%')
                                .padding(8)
                                .backgroundColor('#E8F5E9')
                                .borderRadius(4)
                        }
                        .width('100%')
                        .padding(12)
                        .backgroundColor('#E8F5E9')
                        .borderRadius(8)
                    }
                    
                    // 性能数据显示
                    if (this.showPerformance && this.performanceData) {
                        Column() {
                            Text('性能对比:')
                                .fontSize(14)
                                .fontWeight(FontWeight.Bold)
                                .width('100%')
                            
                            Text(this.performanceData)
                                .fontSize(12)
                                .fontFamily('monospace')
                                .width('100%')
                                .padding(8)
                                .backgroundColor('#FFF3E0')
                                .borderRadius(4)
                        }
                        .width('100%')
                        .padding(12)
                        .backgroundColor('#FFF3E0')
                        .borderRadius(8)
                    }
                    
                    // 按钮组
                    Row({ space: 12 }) {
                        Button('执行排序')
                            .width('48%')
                            .onClick(() => this.executeMergeSort())
                            .enabled(!this.isLoading)
                        
                        Button('性能演示')
                            .width('48%')
                            .onClick(() => this.executePerformanceDemo())
                            .enabled(!this.isLoading)
                    }
                    .width('100%')
                    
                    // 加载指示器
                    if (this.isLoading) {
                        LoadingProgress()
                            .width(40)
                            .height(40)
                    }
                }
                .width('100%')
                .padding(16)
            }
            .layoutWeight(1)
        }
        .width('100%')
        .height('100%')
        .backgroundColor('#FAFAFA')
    }
}

ArkTS实现的详细说明

ArkTS版本为OpenHarmony鸿蒙平台提供了完整的用户界面。通过@State装饰器，我们可以管理应用的状态，当用户输入改变时，UI会自动更新。这个实现包含了输入数组的输入框，以及算法选择的下拉菜单。

在排序结果的显示中，我们显示了排序后的数组。同时，我们还提供了所有方法的结果对比，这样用户可以验证不同方法的一致性。

性能演示功能允许用户在应用中直接看到不同算法的性能差异。通过对比排序100000个随机数的时间，用户可以清楚地看到不同实现方式的性能表现。

应用场景分析

1. 数据库系统

在数据库系统中，合并排序用于外部排序和多路合并。数据库优化器使用合并排序来处理大规模数据。

2. 操作系统

在操作系统中，合并排序用于进程调度和内存管理。调度器使用合并排序来排序进程优先级。

3. 搜索引擎

在搜索引擎中，合并排序用于文档排序和结果合并。搜索结果需要按相关性排序。

4. 数据流处理

在数据流处理中，合并排序用于处理无限数据流。流处理系统需要对数据进行排序。

5. 并行计算

在并行计算中，合并排序易于并行化，是并行排序的首选算法。多核处理器可以并行执行合并排序。

性能优化建议

1. 选择合适的算法

对于通用排序，使用混合合并排序。对于需要稳定排序，使用基础合并排序。对于内存受限，使用原地合并排序。

2. 使用迭代版本

迭代版本避免了递归调用的开销，性能更好。

3. 使用混合排序

当子数组规模较小时，使用插入排序可以减少递归深度并提高性能。

4. 考虑并行化

合并排序易于并行化，可以在多核处理器上并行执行。

总结

合并排序是计算机科学中最优雅和最稳定的排序算法之一。虽然算法思想相对简单，但其实现涉及多种不同的优化策略，从基础的合并排序到混合合并排序和并行合并排序。

通过在KMP框架下实现这个算法，我们可以在多个平台上使用同一套代码，提高开发效率。混合合并排序是解决大多数排序问题的最优方案，提供了O(n log n)的时间复杂度和更好的实际性能。在OpenHarmony鸿蒙平台上，我们可以通过ArkTS调用Kotlin编译的JavaScript代码，或者直接在ArkTS中实现算法，实现真正的跨平台开发。

掌握这个经典算法的多种变体，不仅能够帮助开发者在面试中获得好成绩，更重要的是能够在实际项目中灵活应用这个算法，解决数据库排序、搜索引擎排序等实际问题。