Mergesort, quicksort, and fuzz testing in Go
I'm thrilled by go 1.18's addition of fuzz testing and wanted to play around with implementing and fuzz testing a few sorting algorithms.
Let's start with a classic recursive implementation of mergesort. Recursive mergesort works by spliting the slice into halves until we're left with a slice of length 0 or 1 which, by definition, is sorted. It then recursively merges the two sorted halves by taking the smaller element from the start of the two slices and calling merge on the remaining elements.
Let's start with the recursive merge of two sorted slices.
func mergeRecursive(first, second []int) []int {
// if the length of either slice is 0, there is
// no merging to be done
if len(first) == 0 {
return second
} else if len(second) == 0 {
return first
}
// take the smaller 0th element and return this element
// followed by the result of merging all remaining elements
if first[0] < second[0] {
return append([]int{first[0]}, mergeRecursive(first[1:], second)...)
}
return append([]int{second[0]}, mergeRecursive(first, second[1:])...)
}
With this, the actual mergesort implementation is quite simple.
func MergesortRecursive(vals []int) []int {
// if the length of vals is 0 or 1, then there's no
// work to be done
if len(vals) < 2 {
return vals
}
// recursively sort the two halves of the slice
// and merge the results together
first := MergesortRecursive(vals[:len(vals)/2])
second := MergesortRecursive(vals[len(vals)/2:])
return mergeRecursive(first, second)
}
Voila! Let's look at an iterative mergesort next. We start again with the merging function. We'll merge the two sorted slices by keeping a pointer into each slice and comparing the elements at each pointer, choosing the smaller element and appending it to the merged slice. We repeat this until we've reached the end of one of the slices.
func mergeIterative(first, second []int) []int {
var firstIter, secondIter int
merged := make([]int, 0, len(first)+len(second))
for firstIter < len(first) && secondIter < len(second) {
if first[firstIter] < second[secondIter] {
merged = append(merged, first[firstIter])
firstIter++
} else {
merged = append(merged, second[secondIter])
secondIter++
}
}
if firstIter == len(first) {
return append(merged, second[secondIter:]...)
}
return append(merged, first[firstIter:]...)
}
Next, we come to our iterative mergesort implementation which is quite interesting. It resembles the recursive solution, in that we break the array up into slices of length 1 and merge two at a time until we are left with a single, sorted slice. Instead of recursively splitting the slice into halves, we'll put each element into a queue as a slice of length 1, pop off two slices a time, merge them, and enqueue the merged slice. We repeat this until we're left with a single slice.
func MergesortIterative(vals []int) []int {
if len(vals) < 2 {
return vals
}
queue := make([][]int, len(vals))
for i := range vals {
queue[i] = []int{vals[i]}
}
for len(queue) > 1 {
// pop off two, merge and enqueue
queue = append(queue, mergeIterative(queue[0], queue[1]))
queue = queue[2:]
}
return queue[0]
}
That's it! Now to verify our implementations. Fuzz testing is extremely powerful because it can generate far more test inputs than a human would be able to write. The tricky part is verifying that the output of our fuzz test is correct, given that we don't know the inputs.
Rather than verifying that our output is a specific value, we can verify properties of our output. We're fortunate that this is easy for sorting functions, because we can use the standard library's sort.IntsAreSorted to verify that our output is sorted. We can also verify that our output has the same length as our input, to ensure we haven't lost or added any elements in our sort implementation.
We expect that our two mergesort implementations function identically,
so we can write a fuzzTest function that will be used to test both.
Our fuzzTest function will take a sorting function as an argument,
allowing us to pass MergesortRecursive and MergesortIterative to
it, to easily test both.
func fuzzSort(f *testing.F, sortFunc func([]int) []int) {
// add a simple seed corpus
f.Add([]byte{4, 3, 2, 1})
f.Fuzz(func(t *testing.T, b []byte) {
// fuzzing only supports byte slice arguments, so we
// convert to an int slice here
vals := make([]int, len(b))
for i := range b {
vals[i] = int(b[i])
}
sortedVals := sortFunc(vals)
if !sort.IntsAreSorted(sortedVals) {
t.Errorf("result is not sorted: %v", sortedVals)
}
if len(vals) != len(sortedVals) {
t.Errorf("input and output should have same # of elements")
}
})
}
Our flexible fuzzSort function makes it very simple to add fuzz
tests for both MergesortRecursive and MergesortIterative.
func FuzzMergesortRecursive(f *testing.F) {
fuzzSort(f, MergesortRecursive)
}
func FuzzMergesortIterative(f *testing.F) {
fuzzSort(f, MergesortIterative)
}
Now we have test coverage for both functions when we run go test!
Let's add one more classic sorting function, quicksort. Quicksort works by choosing a random pivot value in the slice to be sorted. It then partitions the slice into elements less than the pivot, equal to the pivot, and greater than the pivot. It recursively sorts the slices less than and greater than the pivot, and combines all of the resulting sorted slices.
func Quicksort(vals []int) []int {
if len(vals) < 2 {
return vals
}
pivot := vals[rand.Intn(len(vals))]
var lt, eq, gt []int
for _, val := range vals {
if val < pivot {
lt = append(lt, val)
} else if val > pivot {
gt = append(gt, val)
} else {
eq = append(eq, val)
}
}
return append(append(Quicksort(lt), eq...), Quicksort(gt)...)
}
Given our flexible fuzzSort, it's super simple to add a test case
for Quicksort.
func FuzzQuicksort(f *testing.F) {
fuzzSort(f, Quicksort)
}