Published
- 4 min read
Merge Sort using Goroutines
Parallel Merge Sort vs Simple Merge Sort
This is a simple example of how to use goroutines to parallelize a merge sort algorithm. We compare the performance of a simple merge sort algorithm with a parallel merge sort algorithm that uses goroutines.
The Merge Sort Algorithm
The merge sort algorithm is a divide and conquer algorithm that recursively splits the input array into two halves, sorts each half, and then merges the two sorted halves into a single sorted array.
To speed up the merge sort algorithm, we use insertion sort for small subarrays (less than 12 elements).
The implementation of the algorithm uses generics to allow sorting of any type of numbers.
func MergeSort[T Number](items []T) []T {
size := len(items)
if size < 2 {
return items
}
if size < K {
return Insertionsort(items)
}
middle := size / 2
var a = MergeSort(items[:middle])
var b = MergeSort(items[middle:])
return merge(a, b)
}
The Merge Sort Algorithm with Goroutines
The parallel merge sort algorithm uses goroutines to sort the two halves of the input array in parallel.
To prevent the creation of too many goroutines, we use a threshold to determine when to use goroutines. If the size of the input array is less than the threshold, we use a simple merge sort algorithm instead of a parallel one.
Here we use a threshold of 512 elements. We can benchmark the performance of the algorithm with different thresholds to find the optimal threshold, but we will not do that in this example.
// ParallelMerge Perform merge sort on a slice using goroutines
func ParallelMerge[T Number](items []T) []T {
if len(items) < 2 {
return items
}
// Use a simple merge sort algorithm if the size of the input array is less than the threshold
if len(items) < 512 {
return MergeSort(items)
}
// Create the wait group to wait for the goroutines to finish
var wg sync.WaitGroup
wg.Add(1)
var middle = len(items) / 2 // Find the middle index of the input array
var a []T // Create a slice to hold the first half of the input array
go func() { // Create a goroutine to sort the first half of the input array
defer wg.Done() // Decrement the wait group counter when the goroutine finishes
a = ParallelMerge(items[:middle]) // Sort the first half of the input array
}()
var b = ParallelMerge(items[middle:]) // Sort the second half of the input array
wg.Wait() // Wait for the goroutine to finish
return merge(a, b) // Merge the two sorted halves
}
Benchmarking the Merge Sort Algorithms
Now we can benchmark our merge sort algorithms to compare their performance.
To benchmark the algorithms, we use arrays of different sizes and measure the time it takes to sort the arrays.
To run the benchmark we use the following command:
go test -bench=. -benchtime 5s > benchmark.txt && benchstat benchmark.txt
Benchstat is a tool that can be used to compare the results of benchmarks.
The results of the benchmark are as follows:
name time/op
Mergesort/1000 14.6µs ± 0%
Mergesort/10000 473µs ± 0%
Mergesort/100000 6.33ms ± 0%
Mergesort/1000000 87.4ms ± 0%
MergesortWithGoroutines/1000 18.7µs ± 0%
MergesortWithGoroutines/10000 217µs ± 0%
MergesortWithGoroutines/100000 2.71ms ± 0%
MergesortWithGoroutines/1000000 29.0ms ± 0%
As we can see, the parallel merge sort algorithm is much faster than the simple merge sort algorithm for large arrays.
Why is the Parallel Merge Sort Algorithm Faster?
The parallel merge sort algorithm is faster because it uses goroutines to sort the two halves of the input array in parallel. The simple merge sort algorithm sorts the two halves of the input array sequentially.
As discussed in the previous article, the cost of creating a goroutine can be high. So we should use a parallel merge sort algorithm only when the size of the input array is large enough to justify the cost of creating goroutines.
Conclusion
In this example, we have seen how to use goroutines to parallelize a merge sort algorithm. We have also benchmarked the performance of the merge sort algorithms to compare their performance. Goroutines are a powerful tool that should be used only when the cost of creating goroutines is justified by the performance improvement.
In this example, the code isn’t more complex when using goroutines therefore it’s worth using them.
Code
The code for this article can be found on GitHub