A common mistake is assuming that parallel merge sort is automatically faster. Merge sort repeatedly splits a collection into two sublists, recursively sorts each sublist, and merges the sorted results. Its independent recursive workloads make concurrency possible, but goroutine and synchronization overhead can outweigh the benefit. section 8.2.2
Figure 8.7 Applying the merge sort algorithm repeatedly breaks each list into two sublists. Then the algorithm uses a merge operation such that the resulting list is sorted.
The split-and-merge structure shows why each recursive half can be processed independently before the final merge. section 8.2.2
func sequentialMergesort(s []int) {
if len(s) <= 1 {
return
}
middle := len(s) / 2
sequentialMergesort(s[:middle]) #1
sequentialMergesort(s[middle:]) #2
merge(s, middle) #3
}
func merge(s []int, middle int) {
// ...
}
The sequential implementation recursively sorts both slices, then merges them. section 8.2.2
When parallelism loses
A first parallel implementation starts two goroutines and waits with sync.WaitGroup before merging. On 10,000 elements, it benchmarks at 17,525,998,709 ns/op versus 2,278,993,555 ns/op sequentially. A practical fix is a cutoff: use sequential merge sort for slices of 2,048 elements or fewer, and parallelize only larger workloads. 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)
}
}
The cutoff implementation limits goroutine creation while retaining parallel recursion for larger slices. section 8.2.2
