A parallelization threshold prevents a costly mistake: launching goroutines for work too small to benefit from concurrency. Below the threshold, merge-sort partitions run sequentially; at or above it, they split into concurrent tasks. section 8.2.2
Use the threshold in parallel merge sort
A Go implementation sets max to 2,048 and calls sequentialMergesort when len(s) <= max; larger slices continue recursively with goroutines and a WaitGroup. This version benchmarks at 1.313 seconds per operation versus 2.279 seconds sequentially and 17.526 seconds for unrestricted parallelism. section 8.2.2
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 threshold branch alongside the parallel recursive implementation. section 8.2.2
