QuickSort algorithm in Go

quicksort.go

package api

import "math/rand"

// QuickSort is a divide-&-conquer algorithm running in O(n log n) time that receives an integer slice
// and returns a sorted slice of integers (h/t: https://gist.github.com/vderyagin/4161347)
func QuickSort(numbers []int) []int {
	length := len(numbers)

	/* BASE CASE */
	if length < 2 {
		return numbers
	}

	/* RECURSIVE CASES */
	pivot := numbers[rand.Intn(length)]
	left := make([]int, 0, length)
	middle := make([]int, 0, length)
	right := make([]int, 0, length)

	// sort the items in their appropriate slice
	for _, item := range numbers {
		switch {
		case item < pivot:
			left = append(left, item)
		case item == pivot:
			middle = append(middle, item)
		case item > pivot:
			right = append(right, item)
		}
	}

	// recursively sort the divided slices
	left, right = QuickSort(left), QuickSort(right)

	// merge into a single sorted slice
	left = append(left, middle...)
	left = append(left, right...)

	return left
}

quicksort_test.go

package api

import (
	"fmt"
	"reflect"
	"testing"
)

var testcases = []struct {
	name   string
	input  []int
	output []int
}{
	{
		name:   "empty slices",
		input:  []int{},
		output: []int{},
	},
	{
		name:   "single-element slices",
		input:  []int{671},
		output: []int{671},
	},
	{
		name:   "multi-element slices",
		input:  []int{64, 12, 32, 4, 23, 11, 98, 5, 43},
		output: []int{4, 5, 11, 12, 23, 32, 43, 64, 98},
	},
}

func TestQuickSort(t *testing.T) {
	t.Run("test cases", func(t *testing.T) {
		for _, tc := range testcases {
			got := QuickSort(tc.input)
			want := tc.output

			if !reflect.DeepEqual(got, want) {
				t.Errorf("got: %v | want: %v", got, want)
			}
		}
	})
}

func ExampleQuickSort() {
	fmt.Println(QuickSort([]int{9, 8, 7, 6, 5, 4, 3, 2, 1}))
	// Output: [1 2 3 4 5 6 7 8 9]
}

func BenchmarkQuickSort(b *testing.B) {
	for i := 0; i < b.N; i++ {
		QuickSort([]int{9, 8, 7, 6, 5, 4, 3, 2, 1})
	}
}