Search⌘ K
AI Features

Solution Review: Merge Sort

Explore how to implement concurrency in the merge sort algorithm using Go. Understand dividing tasks with goroutines and synchronizing them with channels to ensure efficient and correct execution of concurrent code.

We'll cover the following...
Go (1.6.2)
package main
import "fmt"
func Merge(left, right [] int) [] int{
merged := make([] int, 0, len(left) + len(right))
for len(left) > 0 || len(right) > 0{
if len(left) == 0 {
return append(merged,right...)
}else if len(right) == 0 {
return append(merged,left...)
}else if left[0] < right[0] {
merged = append(merged, left[0])
left = left[1:]
}else{
merged = append(merged, right [0])
right = right[1:]
}
}
return merged
}
func MergeSort(data [] int) [] int {
if len(data) <= 1 {
return data
}
done := make(chan bool)
mid := len(data)/2
var left [] int
go func(){
left = MergeSort(data[:mid])
done <- true
}()
right := MergeSort(data[mid:])
<-done
return Merge(left,right)
}
func main(){
data := [] int{9,4,3,6,1,2,10,5,7,8}
fmt.Printf("%v\n%v\n", data, MergeSort(data))
}

Let’s go over the changes we made to the MergeSort function.

Firstly, in merge sort, we keep dividing our array recursively into the right side and the left side and call the MergeSort function on both sides from line 30 to ...