CODEWITHSUNDEEP
goconcurrencymergesort
swappy
swappy

Reputation: 135

How to fix concurrent merge sort in go

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

Upvotes: 1

Views: 473

Answers (1)

Volker
Volker

Reputation: 42412

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

Upvotes: 1

Related Questions