Parallel merge sort divides a list into independent slices, sorts the halves concurrently in goroutines, waits with sync.WaitGroup, and merges them afterward. The structure permits concurrency, but creating goroutines for every recursive split can cost more than it saves. section 8.2.2
The small-task mistake
On 10,000 elements, the unrestricted parallel version takes 17,525,998,709 ns/op versus 2,278,993,555 ns/op sequentially. A cutoff at 2,048 elements lets smaller partitions use sequentialMergesort; the benchmark falls to 1,313,010,260 ns/op.
const max = 2048 #1
func parallelMergesortV2(s []int) {
if len(s) <= 1 {
return
}
if len(s) <= max {
sequentialMergesort(s) #2
} else { #3
middle := len(s) / 2
var wg sync.WaitGroup
wg.Add(2)
go func() {
defer wg.Done()
parallelMergesortV2(s[:middle])
}()
go func() {
defer wg.Done()
parallelMergesortV2(s[middle:])
}()
wg.Wait()
merge(s, middle)
}
}
Inspect the cutoff implementation that limits goroutine creation and delegates small partitions to sequential merge sort. section 8.2.2
