Go语言归并排序实现异常排查：输出结果不符合预期

尝试用Go实现归并排序时，输出结果不符合预期。例如对未排序数组[5, 2, 8, 3, 1, 7, 4, 11, 9, 10]排序，得到结果[1 1 1 1 1 4 4 9 9 10]，而非正确排序结果。以下是待排查的函数代码：

func merge_sort(array []uint) []uint {
    if len(array) > 1 {
        r := len(array) / 2
        L := array[:r]
        M := array[r:]

        L = merge_sort(L)
        M = merge_sort(M)

        i, j, k := 0, 0, 0
        for i < len(L) && j < len(M) {
            if L[i] <= M[j] {
                array[k] = L[i]
                i++
            } else {
                array[k] = M[j]
                j++
            }
            k++
        }
        for i < len(L) {
            array[k] = L[i]
            i++
            k++
        }
        for j < len(M) {
            array[k] = M[j]
            j++
            k++
        }
    }

    return array
}

问题根源 #

Go中切片是引用类型，L := array[:r]和M := array[r:]创建的切片与原数组共享底层存储空间。递归排序L和M时，会直接修改原数组的元素；后续merge阶段往原数组写入合并结果时，会覆盖之前递归排序产生的正确数据，最终导致输出出现大量重复值。

修复方案 #

为L和M创建独立的底层数组，避免与原数组共享存储空间。通过make创建新切片，并用copy复制原切片的内容即可。

修正后的代码：

func merge_sort(array []uint) []uint {
    if len(array) > 1 {
        r := len(array) / 2
        // 创建新切片并复制原内容，脱离原数组的底层存储
        L := make([]uint, r)
        copy(L, array[:r])
        M := make([]uint, len(array)-r)
        copy(M, array[r:])

        L = merge_sort(L)
        M = merge_sort(M)

        i, j, k := 0, 0, 0
        for i < len(L) && j < len(M) {
            if L[i] <= M[j] {
                array[k] = L[i]
                i++
            } else {
                array[k] = M[j]
                j++
            }
            k++
        }
        for i < len(L) {
            array[k] = L[i]
            i++
            k++
        }
        for j < len(M) {
            array[k] = M[j]
            j++
            k++
        }
    }

    return array
}

说明 #

修改后，L和M拥有独立的底层数组，递归排序时仅修改自身切片的元素，不会影响原数组。merge阶段再将排序后的L和M合并到原数组，即可得到正确的排序结果。

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