Parallel Merge Sort vs Simple Merge Sort#

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.

1
func MergeSort[T Number](items []T) []T {
2
  size := len(items)
3
  if size < 2 {
4
    return items
5
  }
6

7
  if size < K {
8
    return Insertionsort(items)
9
  }
10

11
  middle := size / 2
12
  var a = MergeSort(items[:middle])
13
  var b = MergeSort(items[middle:])
14

15
  return merge(a, b)
16
}

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.

1
// ParallelMerge Perform merge sort on a slice using goroutines
2
func ParallelMerge[T Number](items []T) []T {
3
  if len(items) < 2 {
4
    return items
5
  }
6

7
  // Use a simple merge sort algorithm if the size of the input array is less than the threshold
8
  if len(items) < 512 {
9
    return MergeSort(items)
10
  }
11

12
  // Create the wait group to wait for the goroutines to finish
13
  var wg sync.WaitGroup
14
  wg.Add(1)
15

16
  var middle = len(items) / 2  // Find the middle index of the input array
17
  var a []T                   // Create a slice to hold the first half of the input array
18
  go func() {                // Create a goroutine to sort the first half of the input array
19
    defer wg.Done()       // Decrement the wait group counter when the goroutine finishes
20
    a = ParallelMerge(items[:middle]) // Sort the first half of the input array
21
  }()
22
  var b = ParallelMerge(items[middle:]) // Sort the second half of the input array
23

24
  wg.Wait() // Wait for the goroutine to finish
25
  return merge(a, b) // Merge the two sorted halves
26
}

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:

1
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:

1
name                                   time/op
2
Mergesort/1000                     14.6µs ± 0%
3
Mergesort/10000                     473µs ± 0%
4
Mergesort/100000                   6.33ms ± 0%
5
Mergesort/1000000                  87.4ms ± 0%
6

7
MergesortWithGoroutines/1000       18.7µs ± 0%
8
MergesortWithGoroutines/10000       217µs ± 0%
9
MergesortWithGoroutines/100000     2.71ms ± 0%
10
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