Go语言归并排序教程：避免递归栈溢出与正确实现

func MergeSort(slice []int, first, last int) {
    if len(slice) < 2 { // 基本情况，如果切片长度小于2，则已排序
        return
    }

    if first < last { // 递归条件
        mid := len(slice) / 2 // 错误：这里计算的是原始切片的中间索引
        MergeSort(slice, first, mid)
        MergeSort(slice, mid+1, last)
        Merge(slice, first, mid, last)
    }
}

mid := first + (last - first) / 2

// MergeSort 对 slice 中 [first, last] 区间内的元素进行归并排序
func MergeSort(slice []int, first, last int) {
    if first < last { // 如果 first 小于 last，表示区间内至少有两个元素
        // 正确计算中间索引
        mid := first + (last - first) / 2

        // 递归地对左半部分进行排序
        MergeSort(slice, first, mid)
        // 递归地对右半部分进行排序
        MergeSort(slice, mid+1, last)
        // 合并两个已排序的子数组
        Merge(slice, first, mid, last)
    }
}

// Merge 将 slice 中 [p, q] 和 [q+1, r] 两个已排序的子数组合并成一个已排序的数组
func Merge(slice []int, p, q, r int) {
    n1 := q - p + 1 // 左子数组的长度
    n2 := r - q     // 右子数组的长度

    // 创建临时数组 L 和 R
    // 注意：Go中数组/切片索引从0开始，CLRS伪代码从1开始，需要调整
    L := make([]int, n1)
    R := make([]int, n2)

    // 填充左子数组 L
    for i := 0; i < n1; i++ {
        L[i] = slice[p+i]
    }
    // 填充右子数组 R
    for j := 0; j < n2; j++ {
        R[j] = slice[q+1+j]
    }

    i, j := 0, 0 // L 和 R 的当前索引
    // 合并 L 和 R 到原始切片 slice 的 [p, r] 区间
    for k := p; k <= r; k++ {
        // 检查 L 和 R 是否还有元素，并比较大小
        if i < n1 && (j >= n2 || L[i] <= R[j]) {
            slice[k] = L[i]
            i++
        } else {
            slice[k] = R[j]
            j++
        }
    }
}

package main

import (
    "fmt"
    "math/rand"
    "time"
)

// MergeSort 对 slice 中 [first, last] 区间内的元素进行归并排序
func MergeSort(slice []int, first, last int) {
    if first < last {
        mid := first + (last - first) / 2 // 正确计算中间索引
        MergeSort(slice, first, mid)
        MergeSort(slice, mid+1, last)
        Merge(slice, first, mid, last)
    }
}

// Merge 将 slice 中 [p, q] 和 [q+1, r] 两个已排序的子数组合并成一个已排序的数组
func Merge(slice []int, p, q, r int) {
    n1 := q - p + 1
    n2 := r - q

    L := make([]int, n1)
    R := make([]int, n2)

    for i := 0; i < n1; i++ {
        L[i] = slice[p+i]
    }
    for j := 0; j < n2; j++ {
        R[j] = slice[q+1+j]
    }

    i, j := 0, 0
    for k := p; k <= r; k++ {
        if i < n1 && (j >= n2 || L[i] <= R[j]) {
            slice[k] = L[i]
            i++
        } else {
            slice[k] = R[j]
            j++
        }
    }
}

func main() {
    // 示例1：小型数组
    arr1 := []int{9, -13, 4, -2, 3, 1, -10, 21, 12}
    fmt.Println("原始数组1:", arr1)
    MergeSort(arr1, 0, len(arr1)-1)
    fmt.Println("排序后数组1:", arr1) // 预期输出: [-13 -10 -2 1 3 4 9 12 21]

    fmt.Println("--------------------")

    // 示例2：大型随机数组，测试栈溢出修复
    rand.Seed(time.Now().UnixNano())
    largeArr := make([]int, 100000) // 尝试一个较大的数组
    for i := 0; i < len(largeArr); i++ {
        largeArr[i] = rand.Intn(200000) - 100000 // 生成-100000到99999的随机数
    }
    // fmt.Println("原始大型数组 (部分):", largeArr[:10], "...")
    fmt.Println("开始对大型数组进行归并排序...")
    MergeSort(largeArr, 0, len(largeArr)-1)
    fmt.Println("大型数组排序完成。")
    // fmt.Println("排序后大型数组 (部分):", largeArr[:10], "...")

    // 验证排序是否正确（可选）
    isSorted := true
    for i := 0; i < len(largeArr)-1; i++ {
        if largeArr[i] > largeArr[i+1] {
            isSorted = false
            break
        }
    }
    fmt.Println("大型数组是否已排序:", isSorted)
}