Go 语言中归并排序 Merge 函数的切片陷阱与正确实现

func Merge(toSort *[]int, p, q, r int) {
    arr := *toSort // 获取底层切片
    L := arr[p:q]   // L 是 arr 的一个子切片视图
    R := arr[q:r+1] // R 也是 arr 的一个子切片视图

    // 调试输出，观察 L 和 R 的初始内容
    // fmt.Println("L (initial):", L)
    // fmt.Println("R (initial):", R)

    i := 0 // L 的当前索引
    j := 0 // R 的当前索引

    // 从 p 到 r 遍历，将合并后的元素写回 arr
    for index := p; index <= r; index++ {
        if i >= len(L) { // L 已遍历完，将 R 中剩余元素复制过来
            arr[index] = R[j]
            j += 1
            continue
        } else if j >= len(R) { // R 已遍历完，将 L 中剩余元素复制过来
            arr[index] = L[i]
            i += 1
            continue
        }

        // 比较 L 和 R 的当前元素，将较小者写回 arr
        if L[i] > R[j] {
            // fmt.Println("right smaller, writing", R[j])
            arr[index] = R[j]
            j += 1
            continue
        }
        if L[i] <= R[j] {
            // fmt.Println("left smaller, writing", L[i])
            arr[index] = L[i]
            i += 1
            continue
        }
    }
}

func MergeCorrect(toSort []int, p, q, r int) {
    // 1. 创建左右子切片的独立副本
    // 计算左子切片的长度 (q - p)
    leftLen := q - p
    // 创建一个新的切片 left，并复制 toSort[p:q] 的内容
    left := make([]int, leftLen)
    copy(left, toSort[p:q])

    // 计算右子切片的长度 (r - q + 1)
    rightLen := r - q + 1
    // 创建一个新的切片 right，并复制 toSort[q:r+1] 的内容
    right := make([]int, rightLen)
    copy(right, toSort[q:r+1])

    // 2. 初始化左右子切片的指针
    i := 0 // left 切片的当前索引
    j := 0 // right 切片的当前索引

    // 3. 将合并后的元素写回原始的 toSort 切片
    // 遍历 toSort 切片中需要合并的范围 [p, r]
    for k := p; k <= r; k++ {
        // 如果左子切片已全部合并完
        if i >= len(left) {
            toSort[k] = right[j]
            j++
            continue
        }
        // 如果右子切片已全部合并完
        if j >= len(right) {
            toSort[k] = left[i]
            i++
            continue
            // 注意：这里也可以直接 break，因为剩余的都是左子切片中未处理的元素
            // 但为了代码对称性，保持与右子切片处理方式一致
        }

        // 比较左右子切片的当前元素，将较小者放入 toSort[k]
        // 使用 <= 确保归并排序的稳定性（相同元素保持原有相对顺序）
        if left[i] <= right[j] {
            toSort[k] = left[i]
            i++
        } else {
            toSort[k] = right[j]
            j++
        }
    }
}

package main

import "fmt"

// MergeCorrect 是一个正确的归并函数实现
func MergeCorrect(toSort []int, p, q, r int) {
    leftLen := q - p
    left := make([]int, leftLen)
    copy(left, toSort[p:q])

    rightLen := r - q + 1
    right := make([]int, rightLen)
    copy(right, toSort[q:r+1])

    i := 0
    j := 0

    for k := p; k <= r; k++ {
        if i >= len(left) {
            toSort[k] = right[j]
            j++
            continue
        }
        if j >= len(right) {
            toSort[k] = left[i]
            i++
            continue
        }

        if left[i] <= right[j] {
            toSort[k] = left[i]
            i++
        } else {
            toSort[k] = right[j]
            j++
        }
    }
}

// 归并排序主函数 (为完整性提供，实际应用中会递归调用 MergeCorrect)
func MergeSort(arr []int, p, r int) {
    if p < r {
        q := (p + r) / 2
        MergeSort(arr, p, q)
        MergeSort(arr, q+1, r)
        MergeCorrect(arr, p, q, r) // 调用修正后的 Merge 函数
    }
}

func main() {
    arr := []int{1, 7, 14, 15, 44, 65, 79, 2, 3, 6, 55, 70}
    fmt.Println("原始数组:", arr)

    // 假设我们只对 arr 的一部分进行合并，例如 [0, 6] 和 [7, 11]
    // 实际归并排序会递归调用
    // 为了演示 MergeCorrect，我们可以模拟一次合并
    // p=0, q=7, r=11 对应合并 arr[0:7] 和 arr[7:12]
    MergeCorrect(arr, 0, 7, 11)
    fmt.Println("合并后数组:", arr) // 期望: [1 2 3 6 7 14 15 44 55 65 70 79]

    // 完整的归并排序示例
    arr2 := []int{38, 27, 43, 3, 9, 82, 10}
    fmt.Println("原始数组2:", arr2)
    MergeSort(arr2, 0, len(arr2)-1)
    fmt.Println("归并排序后数组2:", arr2) // 期望: [3 9 10 27 38 43 82]
}

原始数组: [1 7 14 15 44 65 79 2 3 6 55 70]
合并后数组: [1 2 3 6 7 14 15 44 55 65 70 79]
原始数组2: [38 27 43 3 9 82 10]
归并排序后数组2: [3 9 10 27 38 43 82]