请求详解Go语言并发归并排序中的merge函数

我是并发编程新手，正在学习Go语言的并发归并排序实现，对代码里merge函数末尾的for ok1 || ok2循环逻辑感到困惑，恳请详细讲解该merge函数的执行机制。相关代码如下：

package main

import (
    "fmt"
    "math/rand"
    "time"
)

func merge(a []int, ch chan int) {
    //     defer close(ch)
    if len(a) == 0 {
        close(ch)
        return
    }

    if len(a) == 1 {
        ch <- a[0]
        close(ch)
        return
    }

    mid := len(a) / 2

    ch1 := make(chan int)
    go merge(a[:mid], ch1)

    ch2 := make(chan int)
    go merge(a[mid:], ch2)

    v1, ok1 := <-ch1
    v2, ok2 := <-ch2

    for ok1 || ok2 {
        if (ok1 && ok2 && v1 < v2) || (ok1 && !ok2) {
            fmt.Printf("v1 = %v, ch = %v", v1, ch)
            ch <- v1
            v1, ok1 = <-ch1
        } else if (ok1 && ok2 && v1 >= v2) || (!ok1 && ok2) {
            ch <- v2
            v2, ok2 = <-ch2
            fmt.Printf("v2 = %v, ch = %v", v2, ch)
        }
    }
    close(ch)
}

func Merge(a []int) (sorted []int) {
    ch := make(chan int)
    go merge(a, ch)

    for v := range ch {
        sorted = append(sorted, v)
    }
    return
}

func generateSlice(size int) []int {

    slice := make([]int, size)
    rand.Seed(time.Now().UnixNano())
    for i := 0; i < size; i++ {
        slice[i] = rand.Intn(999) - rand.Intn(999)
    }
    return slice
}

func main() {
    slice := generateSlice(10)
    start := time.Now()
    sorted := Merge(slice)
    fmt.Printf("Time taken to sort: %v, sorted: %v", time.Since(start), sorted)
}

整体执行逻辑铺垫 #

这个并发归并排序的核心思路是递归拆分数组+goroutine并行排序+通道传递有序元素：

• 递归把原数组拆分成两半，每半启动一个goroutine单独排序，结果通过各自的通道ch1、ch2输出
• 当前merge函数的任务就是把两个通道里的有序元素，按从小到大的顺序合并到当前通道ch中，最后返回给上层

重点讲解for ok1 || ok2循环 #

1. 循环前的初始化

v1, ok1 := <-ch1
v2, ok2 := <-ch2

这两行是从两个子通道各读取第一个元素：

• v1/v2是读取到的元素值
• ok1/ok2是布尔值：如果通道未关闭且还有元素可读，ok为true；如果通道已关闭且没有剩余元素，ok为false

2. 循环条件ok1 || ok2

这个条件的意思是：只要两个通道中还有任意一个有元素可读，就继续循环。直到两个通道都被读完（ok1和ok2同时为false），循环才会终止。

3. 循环内的分支逻辑

循环里的两个分支，本质是实现归并排序的核心合并逻辑——从两个有序序列中每次取较小的元素，直到其中一个序列耗尽，再把另一个序列的剩余元素全部输出：

• 第一个分支：(ok1 && ok2 && v1 < v2) || (ok1 && !ok2)

  • 两种情况会进入这个分支：
    1. 两个通道都还有元素，且v1比v2小
    2. 只有ch1还有元素（ch2已经读完）
  • 执行动作：把v1发送到当前通道ch，然后从ch1读取下一个元素，更新v1和ok1的值

• 第二个分支：(ok1 && ok2 && v1 >= v2) || (!ok1 && ok2)

  • 两种情况会进入这个分支：
    1. 两个通道都还有元素，且v2小于等于v1
    2. 只有ch2还有元素（ch1已经读完）
  • 执行动作：把v2发送到当前通道ch，然后从ch2读取下一个元素，更新v2和ok2的值

4. 循环结束后的收尾

循环终止时，ch1和ch2的元素都已经全部读取并合并到ch中，此时调用close(ch)关闭当前通道，这样上层通过range ch读取元素的逻辑会在通道关闭后自动终止，避免阻塞。

补充说明几个细节 #

• 当子数组长度为1时，直接把元素发送到通道后关闭通道，这是递归的终止条件
• 当子数组为空时，直接关闭通道，避免上层读取阻塞
• 每个merge函数负责关闭自己的通道，保证通道的关闭逻辑和发送逻辑在同一个goroutine中，符合Go的通道使用规范

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