深入理解Go语言切片行为：修复合并排序算法中的常见陷阱

func Merge(toSort *[]int, p, q, r int) {
    arr := *toSort
    L := arr[p:q]       // L 是 arr 的一个子切片
    R := arr[q:r+1]     // R 也是 arr 的一个子切片
    // ... 合并逻辑 ...
    // arr[index] = ...  // 写入 arr 会影响 L 和 R 读取到的值
}

package main

import "fmt"

// Merge 函数用于合并两个已排序的子序列
// toSort: 待排序的切片
// p: 第一个子序列的起始索引
// q: 第一个子序列的结束索引 + 1 (即第二个子序列的起始索引)
// r: 第二个子序列的结束索引
func Merge(toSort []int, p, q, r int) {
    // 创建左子序列和右子序列的副本
    // 这样做是为了避免在原地合并时，对 arr 的修改影响 L 和 R 的读取
    // 尤其是在 L 和 R 都是 arr 的子切片时
    leftLen := q - p
    rightLen := r - q + 1 // 注意这里是 r - q + 1，因为 r 是包含的

    // 如果 leftLen 或 rightLen 为负数，说明参数 p, q, r 有问题
    if leftLen < 0 || rightLen < 0 {
        // 可以选择 panic 或返回错误，这里为了示例直接返回
        fmt.Println("Error: Invalid p, q, r parameters for Merge function.")
        return
    }

    // 创建 L 和 R 的实际副本
    // 使用 make 创建新的底层数组，并使用 copy 复制数据
    L := make([]int, leftLen)
    copy(L, toSort[p:q])

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

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

    // 将 L 和 R 中的元素合并回 toSort[p...r]
    for k := p; k <= r; k++ {
        // 如果 L 已经遍历完，则将 R 中剩余的元素全部复制到 toSort
        if i >= len(L) {
            toSort[k] = R[j]
            j++
        } else if j >= len(R) { // 如果 R 已经遍历完，则将 L 中剩余的元素全部复制到 toSort
            toSort[k] = L[i]
            i++
        } else if L[i] <= R[j] { // 比较 L 和 R 的当前元素，将较小的放入 toSort
            toSort[k] = L[i]
            i++
        } else { // R[j] 更小
            toSort[k] = R[j]
            j++
        }
    }
}

// 完整的归并排序主函数 (可选，用于测试 Merge 函数)
func MergeSort(arr []int, p, r int) {
    if p < r {
        q := (p + r) / 2
        MergeSort(arr, p, q)
        MergeSort(arr, q+1, r) // 注意这里是 q+1
        Merge(arr, p, q+1, r)  // Merge 函数的 q 参数是第二个子序列的起始索引
    }
}

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

    // 假设我们只对 arr 的一部分进行合并，例如 arr[0:8] 和 arr[8:12]
    // 对应 p=0, q=8, r=11 (因为切片索引是 [p, q-1] 和 [q, r])
    // 这里的 q 应该对应 Merge 函数中第二个子序列的起始索引
    // 所以对于 {1,7,14,15,44,65,79,2} 和 {3,6,55,70}
    // p=0, q_middle=7 (第一个子序列的最后一个索引), r=11
    // Merge(arr, p, q_middle + 1, r)
    // 原始问题中的 q 参数是 arr[p:q] 的结束索引，同时也是 arr[q:r+1] 的起始索引
    // 所以在调用 Merge 时，q 应该传入第二个子序列的起始索引
    // 对于 arr := []int{1,7,14,15,44,65,79,2,3,6,55,70}
    // 假设我们要合并 [1,7,14,15,44,65,79,2] 和 [3,6,55,70]
    // 第一个子序列: arr[0...7]
    // 第二个子序列: arr[8...11]
    // 所以 p=0, q=8, r=11
    Merge(arr, 0, 8, 11) // 调用合并函数

    fmt.Println("Merged array:", arr) // 期望输出: [1 2 3 6 7 14 15 44 55 65 70 79]

    // 完整的归并排序示例
    data := []int{38, 27, 43, 3, 9, 82, 10}
    fmt.Println("\nOriginal data for MergeSort:", data)
    MergeSort(data, 0, len(data)-1)
    fmt.Println("Sorted data by MergeSort:", data)
}