Go并发归并排序程序挂起，添加fmt调用后恢复正常，求解释

问题描述 #

实现并发归并排序时，非并发版本逻辑验证正确，但并发版运行时会挂起数秒后被终止（signal: killed）。奇怪的是，在mergeSort函数的基准判断中添加fmt调用后，程序能正常输出正确排序结果并退出。

错误代码 #

package main
import (
  "fmt"
)

func merge(a []int, b []int) []int {
  var aCounter int = 0
  var bCounter int = 0

  var newArray []int = []int{}
  
  for aCounter < len(a) || bCounter < len(b) {
    if aCounter >= len(a) {
      newArray = append(newArray, b[bCounter])
      bCounter++
    } else if bCounter >= len(b) {
      newArray = append(newArray, a[aCounter])
      aCounter++
    } else {
      if a[aCounter] < b[bCounter] {
        newArray = append(newArray, a[aCounter])
        aCounter++
      } else {
        newArray = append(newArray, b[bCounter])
        bCounter++
      }
    }
  }

  return newArray
}

func mergeSort(arr []int, c chan []int) {
  if len(arr) == 1 {
    c <- arr
  }

  firstHalfChan := make(chan []int)
  secondHalfChan := make(chan []int)
  
  go mergeSort(arr[0:len(arr)/2], firstHalfChan)
  go mergeSort(arr[len(arr)/2:len(arr)], secondHalfChan)

  firstHalf, secondHalf := <-firstHalfChan, <-secondHalfChan

  c <- merge(firstHalf, secondHalf)
}

func main() {
  s := []int{10, 3, 8, 1, 2, 9}

  channel := make(chan []int)
  go mergeSort(s, channel)

  sorted := <- channel

  fmt.Println(sorted)
}

修改后可运行的代码 #

func mergeSort(arr []int, c chan []int) {
  if len(arr) == 1 {
    fmt.Println(arr) // ADDED
    
    c <- arr
  }

  firstHalfChan := make(chan []int)
  secondHalfChan := make(chan []int)
  
  go mergeSort(arr[0:len(arr)/2], firstHalfChan)
  go mergeSort(arr[len(arr)/2:len(arr)], secondHalfChan)

  firstHalf, secondHalf := <-firstHalfChan, <-secondHalfChan

  c <- merge(firstHalf, secondHalf)
}

错误原因与行为解释 #

1. 核心错误：基准分支未终止函数执行
   在mergeSort的基准条件len(arr) == 1中，执行c <- arr后没有添加return语句，导致代码继续向下执行。此时会：

   • 创建两个新的channel
   • 启动两个goroutine处理arr[0:len(arr)/2]（空切片）和arr[len(arr)/2:len(arr)]（原单元素切片）
   • 对于空切片，len(arr) == 0不会触发基准条件，会继续递归拆分，无限创建goroutine，最终耗尽系统内存/CPU资源，被操作系统以signal: killed终止。

2. 添加fmt后“正常运行”的巧合
   添加fmt.Println(arr)后，fmt的IO操作会触发Go runtime的goroutine调度，同时主goroutine在接收到排序结果后会立即退出，整个进程终止，那些正在无限递归创建的goroutine还没来得及消耗过多资源就被终止，因此看起来程序正常运行。但这只是临时的巧合，并非正确的修复方式。

正确修复方式 #

在基准情况的c <- arr后添加return，终止函数执行，避免后续不必要的递归：

func mergeSort(arr []int, c chan []int) {
  if len(arr) == 1 {
    c <- arr
    return // 必须添加，终止函数
  }

  firstHalfChan := make(chan []int)
  secondHalfChan := make(chan []int)
  
  go mergeSort(arr[0:len(arr)/2], firstHalfChan)
  go mergeSort(arr[len(arr)/2:len(arr)], secondHalfChan)

  firstHalf, secondHalf := <-firstHalfChan, <-secondHalfChan

  c <- merge(firstHalf, secondHalf)
}

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