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.

`CHECK````
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.

`CHECK````
// 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:

`CHECK````
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:

`CHECK````
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