如何修复Go中的并发合并排序

Question

我正在尝试学习 go lang，并面临同时实现合并排序的问题。它没有正确对数组进行排序

我尝试过寻找任何竞争条件，并尝试在各个阶段进行打印。但似乎无法弄清楚这个问题。有什么工具可以分析和指出此类问题。

package main

import (

    "fmt"

    "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

    var t []int

    for ok1 == true && ok2 == true {

        if v1 < v2 {

            ch <- v1

            t = append(t, v1)

            v1, ok1 = <-ch1

        } else {

            ch <- v2

            t = append(t, v2)

            v2, ok2 = <-ch2

        }

    }

    close(ch)

}

func Merge(a []int) (sortedA []int) {

    ch := make(chan int)

    go merge(a, ch)

    for v := range ch {

        sortedA = append(sortedA, v)

    }

    return

}

func main() {

    arr := []int{3, 34, 23, 65, 34, 7, -1, 0, -23}

    start := time.Now()

    b := Merge(arr)

    fmt.Printf("Time taken to sort: %v, sorted: %v", time.Since(start), b)

}

我预计输出是[-23 -1 0 3 7 23 34 34 65]但实际输出只是-23

Answer 1

您的合并阶段已被破坏：您必须发送来自和 的ch所有值，但一旦或中的任何一个耗尽，您的代码就会停止。一旦你耗尽，例如，你必须将所有东西从 发送到。ch1ch2ch1 ch2ch2ch1c一些事情（一定要清理条件！）for ok1 || ok2 {&nbsp; &nbsp; if (ok1 && ok2 && v1 < v2) || (ok1 && !ok2) {&nbsp; &nbsp; &nbsp; &nbsp; ch <- v1&nbsp; &nbsp; &nbsp; &nbsp; v1, ok1 = <-ch1&nbsp; &nbsp; } else if (ok1 && ok2 && v1 >= v2) || (!ok1 && ok2) {&nbsp; &nbsp; &nbsp; &nbsp; ch <- v2&nbsp; &nbsp; &nbsp; &nbsp; v2, ok2 = <-ch2&nbsp; &nbsp; }}