I'm trying to learn more about concurrency in Golang, so I'm trying to improve a MergeSort algorithm to do the sorting concurrently.
My idea is to create a goroutine everytime I split the array in two, so my code is like this:
func mergeSort(arr []int) []int {
if len(arr) <= 1 {
return arr
}
mid := len(arr) / 2
left := arr[:mid]
right := arr[mid:]
orderedLeft := make(chan []int)
orderedRight := make(chan []int)
var wg sync.WaitGroup
wg.Add(2)
go func() {
defer wg.Done()
left = mergeSort(left)
orderedLeft <- left
}()
go func() {
defer wg.Done()
right = mergeSort(right)
orderedRight <- right
}()
wg.Wait()
close(orderedLeft)
close(orderedRight)
left = <-orderedLeft
fmt.Println(left)
right = <-orderedRight
fmt.Println(right)
return merge(left, right)
}
But Im getting a fatal error:
fatal error: all goroutines are asleep - deadlock!
What am I doing wrong?
May get bit confusing because you are mixing two concurrency patterns. I'll get there in a sec.
When you use unbuffered channels, the sender goroutine will block until the receiver goroutine is ready to receive the value.
In this casee, the main goroutine is waiting for the two goroutines to complete using wg.Wait(), while the two goroutines are trying to send their results to the channels orderedLeft and orderedRight. However, since the main goroutine is not actively receiving these values from the channels, the goroutines get blocked and cannot proceed to completion.
You can easily solve this by making the channels buffered: orderedRight := make(chan []int, 1).
However, you can use either channels or waitGroups instead of mixing them, which is not really necessary in this case:
func mergeSort(arr []int) []int {
if len(arr) <= 1 {
return arr
}
mid := len(arr) / 2
left := arr[:mid]
right := arr[mid:]
var wg sync.WaitGroup
wg.Add(2)
go func() {
defer wg.Done()
left = mergeSortWg(left)
}()
go func() {
defer wg.Done()
right = mergeSortWg(right)
}()
wg.Wait()
return merge(left, right)
}