深入理解Go语言切片：解决归并排序中Merge函数的数据覆盖问题

func Merge(toSort *[]int, p, q, r int) {
    arr := *toSort
    L := arr[p:q]       // L 是 arr[p] 到 arr[q-1] 的视图
    R := arr[q:r+1]     // R 是 arr[q] 到 arr[r] 的视图

    // fmt.Println(L) // 调试输出
    // fmt.Println(R) // 调试输出

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

    for index := p; index <= r; index++ { // 从 arr[p] 开始填充到 arr[r]
        if i >= len(L) {
            arr[index] = R[j]
            j += 1
            // continue // 移除 continue，确保逻辑顺序
        } else if j >= len(R) {
            arr[index] = L[i]
            i += 1
            // continue // 移除 continue，确保逻辑顺序
        } else if L[i] > R[j] { // 这里需要注意，原始代码有两层 if
            // fmt.Println("right smaller")
            arr[index] = R[j]
            j += 1
            // continue
        } else { // L[i] <= R[j]
            // fmt.Println("left smaller")
            arr[index] = L[i]
            i += 1
            // continue
        }
    }
}

func MergeCorrectedCopy(toSort *[]int, p, q, r int) {
    arr := *toSort // 获取底层切片

    // 创建 L 和 R 的显式副本
    // L_orig 是原始切片 arr[p:q] 的视图
    // R_orig 是原始切片 arr[q:r+1] 的视图
    L_orig := arr[p:q]
    R_orig := arr[q:r+1]

    // 使用 make 分配新内存，并使用 copy 将元素复制过去
    L := make([]int, len(L_orig))
    copy(L, L_orig) // L 现在是一个独立的切片
    R := make([]int, len(R_orig))
    copy(R, R_orig) // R 现在是一个独立的切片

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

    // 从 arr[p] 开始填充到 arr[r]
    for index := p; index <= r; index++ {
        if i >= len(L) { // L 已遍历完，将 R 中剩余元素放入 arr
            arr[index] = R[j]
            j += 1
        } else if j >= len(R) { // R 已遍历完，将 L 中剩余元素放入 arr
            arr[index] = L[i]
            i += 1
        } else if L[i] <= R[j] { // L[i] 小于或等于 R[j]，将 L[i] 放入 arr
            arr[index] = L[i]
            i += 1
        } else { // L[i] > R[j]，将 R[j] 放入 arr
            arr[index] = R[j]
            j += 1
        }
    }
}

func MergeCorrectedTemp(toSort *[]int, p, q, r int) {
    arr := *toSort // 获取底层切片

    L_part := arr[p:q]       // L_part 仍是 arr 的视图
    R_part := arr[q:r+1]     // R_part 仍是 arr 的视图

    // 创建一个临时切片来存储合并结果
    // 它的长度是 L_part 和 R_part 的总和
    merged := make([]int, len(L_part)+len(R_part))

    i := 0 // L_part 的索引
    j := 0 // R_part 的索引
    k := 0 // merged 的索引

    // 比较 L_part 和 R_part 的元素，将较小的放入 merged
    for i < len(L_part) && j < len(R_part) {
        if L_part[i] <= R_part[j] {
            merged[k] = L_part[i]
            i++
        } else {
            merged[k] = R_part[j]
            j++
        }
        k++
    }

    // 将 L_part 中剩余的元素复制到 merged
    for i < len(L_part) {
        merged[k] = L_part[i]
        i++
        k++
    }
    // 将 R_part 中剩余的元素复制到 merged
    for j < len(R_part) {
        merged[k] = R_part[j]
        j++
        k++
    }

    // 将合并后的结果从 merged 切片复制回原始切片 arr 的 [p:r+1] 范围
    copy(arr[p:r+1], merged)
}