Go语言归并排序实现存在bug，请求帮忙定位问题

核心Bug分析 #

你的归并排序实现存在三个关键问题：

• 递归终止条件错误
  mergeSort 函数中使用 if hi-lo > 1 作为递归判断条件，这会导致子数组长度为2时直接进入交换逻辑，同时遗漏了部分需要递归拆分的场景，且未处理单个元素的合法终止情况。

• Merge阶段比较对象错误
  在merge函数中，你直接调用data.Less(i,j)比较原数组元素，但此时原数组已在递归过程中被修改，正确的做法应该基于临时数组temp（merge前的原始子数组快照）进行比较。

• Less方法不符合接口规范
  IntSlice的Less方法返回x[i] <= x[j]，违反了sort.Interface的约定——Less应返回严格小于的判断，使用<=会导致排序逻辑出现异常，干扰相等元素的处理。

修复后的完整代码 #

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] } // 改为严格小于
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 {
			// 基于临时数组的元素进行比较
			valI := temp[i-lo].(int)
			valJ := temp[j-lo].(int)
			if valI < valJ {
				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 lo < hi { // 修改为通用递归终止条件
		mid := (lo + hi) / 2
		mergeSort(data, lo, mid)
		mergeSort(data, mid+1, hi)
		merge(data, lo, mid, 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) // 输出：[2 6 7 9 9 10 11]
}

修复说明 #

1. 递归终止条件：改为lo < hi，确保所有长度大于1的子数组都会被拆分，单个元素的子数组直接终止递归，无需额外交换操作。
2. Merge比较逻辑：从临时数组temp中取出元素进行比较，避免使用已被修改的原数组数据，保证merge阶段的比较基于原始子数组快照。
3. Less方法修正：将<=改为<，符合sort.Interface的规范，同时避免相等元素的不必要交换，保证排序稳定性。

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