如何修复并发合并排序

Question

I am trying to learn go lang and facing problems in implementing merge sort concurrently. It is not sorting the array properly

I have tried finding any race conditions and also tried printing at various stages. But couldn't seem to figure out the issue. Any tool to analyze and point out such issues.

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)
}

I expected the output to be [-23 -1 0 3 7 23 34 34 65] but the actual output is only -23

Answer 1

Your merge phase is broken: You have to send on ch all values from ch1 and ch2 but your code stops once any of ch1 or ch2 is drained. Once you drained e.g. ch2 you have to send everything from ch1 to c.

Something along (make sure to clean up the conditions!)

for ok1 || ok2 {
    if (ok1 && ok2 && v1 < v2) || (ok1 && !ok2) {
        ch <- v1
        v1, ok1 = <-ch1
    } else if (ok1 && ok2 && v1 >= v2) || (!ok1 && ok2) {
        ch <- v2
        v2, ok2 = <-ch2
    }
}