在 Go 中实现的合并排序算法中找不到错误

Question

我想实现一个归并排序算法，但一直在寻找我的程序无法正确排序的原因。我曾尝试向 ChatGPT 寻求一些建议，但它无法帮助找到错误所在。

package main

import (
    "fmt"
    "sort"
)

// sortable is the interface that must be implemented by a type to be sorted by the merge sort.
type sortable interface {
    sort.Interface
    Set(i int, x any)
    At(i int) any
}

// IntSlice attaches the methods of sortable to []int, sorting in increasing order.
type IntSlice []int

func (x IntSlice) Len() int           { return len(x) }
func (x IntSlice) Less(i, j int) bool { return x[i] <= x[j] } // actually represents the `<=` operator
func (x IntSlice) Swap(i, j int)      { x[i], x[j] = x[j], x[i] }
func (x IntSlice) Set(i int, a any)   { x[i] = a.(int) }
func (x IntSlice) At(i int) any       { return x[i] }

// merge two arrays into one
func merge(data sortable, lo, mid, hi int) {
    temp := make([]any, hi-lo+1)
    for i := lo; i <= hi; i++ {
        temp[i-lo] = data.At(i)
    }
    i, j := lo, mid+1
    for k := lo; k <= hi; k++ {
        if i > mid {
            data.Set(k, temp[j-lo])
            j++
        } else if j > hi {
            data.Set(k, temp[i-lo])
            i++
        } else if data.Less(i, j) { // actually represents the `<=` operator
            data.Set(k, temp[i-lo])
            i++
        } else {
            data.Set(k, temp[j-lo])
            j++
        }
    }
}
// recursive solving method
func mergeSort(data sortable, lo, hi int) {
    if hi-lo > 1 {
        mid := (lo + hi) / 2
        mergeSort(data, lo, mid)
        mergeSort(data, mid+1, hi)
        merge(data, lo, mid, hi)
    } else {
        if !data.Less(lo, hi) { // actually represents the `>` operator
            data.Swap(lo, hi)
        }
    }
}

func SortTtE(data sortable) {
    mergeSort(data, 0, data.Len()-1)
}

func main() {
    a := []int{10, 9, 11, 2, 7, 9, 6}
    SortTtE(IntSlice(a))
    fmt.Println(a)
// the false output: [2 6 9 7 10 11 9]
}

可能是我的控制流程出错了，所以我希望有人能帮我找到错误在哪里。 这是游乐场所在的地方：https://go.dev/play/p/AXZqZH2Ko1E

Answer 1

在

merge

中，您在检查

data

的同时修改数组

data.Less

。这会导致未定义状态，因为您的实际数据在那一刻存储在

temp

中。

要解决此问题，请执行检查

temp

func merge(data sortable, lo, mid, hi int) {
    temp := make([]int, hi-lo+1)
    for i := lo; i <= hi; i++ {
        // Notice I have to cast here, because temp it []int, 
        // but data is an interface
        temp[i-lo] = data.At(i).(int)
    }
    i, j := lo, mid+1
    for k := lo; k <= hi; k++ {
        if i > mid {
            data.Set(k, temp[j-lo])
            j++
        } else if j > hi {
            data.Set(k, temp[i-lo])
            i++
        } else if temp[i-lo] <= temp[j-lo] { // <- here, check against the actual data
            data.Set(k, temp[i-lo])
            i++
        } else {
            data.Set(k, temp[j-lo])
            j++
        }
    }
}