Go语言归并排序转译问题：Python转Go后输出异常求助

我是Go语言新手，通过实践学习该语言。实现归并排序时结果不符合预期，确定问题和slice的使用有关。将可正常运行的Python归并排序代码转译为Go后出现异常，Python代码工作正常，但Go代码输出全是-899，怀疑是对slice的理解有误。

可正常运行的Python代码 #

def mergeSort(arr):
    if len(arr) > 1:
 
         # Finding the mid of the array
        mid = len(arr)//2
 
        # Dividing the array elements
        L = arr[:mid]
 
        # into 2 halves
        R = arr[mid:]
 
        # Sorting the first half
        mergeSort(L)
 
        # Sorting the second half
        mergeSort(R)
 
        i = j = k = 0
 
        # Copy data to temp arrays L[] and R[]
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1
 
        # Checking if any element was left
        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1
 
        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1
 
# Code to print the list
 
 
def printList(arr):
    for i in range(len(arr)):
        print(arr[i], end=" ")
    print()

# Driver Code
arr = [457, 4, 0, 500, -8, 6, 5, -20, -93, 50, 5, 1, 6, 10, 54, 7, 13, 10, -5, 50, 500, 8, 4, -1, -99, 5, 0, 0, -899]
printList(mergeSort(arr))

转译后的Go语言代码 #

package main
import "fmt"

func main() {
    intArr := []int{457, 4, 0, 500, -8, 6, 5, -20, -93, 50, 5, 1, 6, 10, 54, 7, 13, 10, -5, 50, 500, 8, 4, -1, -99, 5, 0, 0, -899}
    fmt.Println(mergeSort(intArr))
}

func mergeSort(arr []int) []int {
    if len(arr) > 1 {

        // Finding the mid of the array
        mid := int(len(arr) / 2)

        // Dividing the array elements
        L := arr[:mid]

        // into 2 halves
        R := arr[mid:]

        // Sorting the first half
        mergeSort(L)

        // Sorting the second half
        mergeSort(R)

        i, j, k := 0, 0, 0

        // Copy data to temp arrays L[] and R[]
        for i < len(L) && j < len(R) {
            if L[i] < R[j] {
                arr[k] = L[i]
                i++
            } else {
                arr[k] = R[j]
                j++
            }
            k++
        }

        // Checking if any element was left
        for i < len(L) {
            arr[k] = L[i]
            i++
            k++
        }

        for j < len(R) {
            arr[k] = R[j]
            j++
            k++
        }
    }
    return arr
}

Go代码输出结果 #

[-899 -899 -899 -899 -899 -899 -899 -899 -899 -899 -899 -899 -899 -899 -899 -899 -899 -899 -899 -899 -899 -899 -899 -899 -899 -899 -899 -899 -899]

问题原因分析 #

核心问题出在Go语言slice的引用特性与Python列表的复制特性差异：

1. Python中L = arr[:mid]和R = arr[mid:]是创建原列表的独立副本，递归排序的是副本，合并时再将结果写回原数组，不会出现数据干扰。
2. Go语言中L := arr[:mid]和R := arr[mid:]并未创建新数组，只是生成了指向原数组底层数据的slice视图。递归调用mergeSort(L)和mergeSort(R)时，修改的是同一个底层数组的不同区域，合并阶段会互相覆盖数据。
3. 额外问题：递归调用mergeSort(L)和mergeSort(R)后，没有接收返回的排序结果，相当于直接忽略了排序操作，合并时用的还是未排序的原始视图数据，最终导致所有位置被最小值覆盖。

修复方案 #

修改两点即可解决问题：

1. 递归调用时接收排序后的slice结果，确保L和R是已排序的独立数据
2. 创建新slice存储合并结果，避免直接修改原数组的视图引发冲突

修复后的代码：

package main
import "fmt"

func main() {
    intArr := []int{457, 4, 0, 500, -8, 6, 5, -20, -93, 50, 5, 1, 6, 10, 54, 7, 13, 10, -5, 50, 500, 8, 4, -1, -99, 5, 0, 0, -899}
    fmt.Println(mergeSort(intArr))
}

func mergeSort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }

    mid := len(arr) / 2
    // 接收递归排序后的结果
    L := mergeSort(arr[:mid])
    R := mergeSort(arr[mid:])

    i, j, k := 0, 0, 0
    // 创建新slice存储合并结果
    merged := make([]int, len(arr))
    
    for i < len(L) && j < len(R) {
        if L[i] < R[j] {
            merged[k] = L[i]
            i++
        } else {
            merged[k] = R[j]
            j++
        }
        k++
    }

    for i < len(L) {
        merged[k] = L[i]
        i++
        k++
    }

    for j < len(R) {
        merged[k] = R[j]
        j++
        k++
    }

    return merged
}

修复说明 #

• 递归调用直接赋值给L和R，确保使用的是已排序的slice
• 用make创建新的mergedslice存储合并结果，彻底避免原数组视图的引用冲突
• 简化边界条件判断，逻辑更清晰

内容的提问来源于stack exchange，提问作者Smarhacker