深入理解Go语言切片：修正归并排序中的合并函数实现

func Merge(toSort *[]int, p, q, r int) {
    arr := *toSort
    L := arr[p:q]         // 左子切片
    R := arr[q:r+1]       // 右子切片

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

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

    for index := p; index <= r; index++ {
        if i >= len(L) {
            arr[index] = R[j]
            j += 1
            continue
        } else if j >= len(R) {
            arr[index] = L[i]
            i += 1
            continue
        }

        if L[i] > R[j] {
            // fmt.Println("right smaller") // 调试输出
            arr[index] = R[j]
            j += 1
        } else { // L[i] <= R[j]
            // fmt.Println("left smaller") // 调试输出
            arr[index] = L[i]
            i += 1
        }
    }
}

package main

import "fmt"

// MergeCorrected 使用辅助切片修正归并排序的合并函数
func MergeCorrected(arr []int, p, q, r int) {
    // 创建一个与待合并区间大小相同的辅助切片
    // 并将 arr[p...r] 的内容复制到 temp 中
    temp := make([]int, r-p+1)
    copy(temp, arr[p:r+1])

    // 定义 temp 中对应 L 和 R 的逻辑子切片
    // 注意：这里的 L_temp 和 R_temp 只是为了方便理解和索引
    // 它们是 temp 的子切片，不再与原始 arr 共享底层数组
    L_temp := temp[0 : q-p]         // 对应 arr[p:q]
    R_temp := temp[q-p : r-p+1]     // 对应 arr[q:r+1]

    i := 0 // L_temp 的当前索引
    j := 0 // R_temp 的当前索引
    k := p // arr 中待写入的当前索引

    // 循环比较 L_temp 和 R_temp 的元素，并将较小者写入 arr[k]
    for i < len(L_temp) && j < len(R_temp) {
        if L_temp[i] <= R_temp[j] {
            arr[k] = L_temp[i]
            i++
        } else {
            arr[k] = R_temp[j]
            j++
        }
        k++
    }

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

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

// 完整的归并排序函数（可选，用于演示 MergeCorrected 的集成）
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
        MergeCorrected(arr, p, q+1, r) // MergeCorrected 的 q 参数是右子数组的起始索引
    }
}

func main() {
    // 示例数据：前一部分已排序，后一部分已排序
    // 用于测试 MergeCorrected 函数
    arr1 := []int{1, 7, 14, 15, 44, 65, 79, 2, 3, 6, 55, 70}
    fmt.Println("原始数组 (MergeCorrected测试):", arr1)

    p1 := 0
    q1 := 7  // arr1[p1:q1] 是 {1,7,14,15,44,65,79}
    r1 := 11 // arr1[q1:r1+1] 是 {2,3,6,55,70}

    // 调用修正后的合并函数
    MergeCorrected(arr1, p1, q1, r1)

    fmt.Println("合并后数组 (MergeCorrected测试):", arr1) // 期望输出: [1 2 3 6 7 14 15 44 55 65 70 79]

    fmt.Println("---")

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