Simple and custom quicksort in Go (GoLang).

quicksort.go

package slice

// For learning purpose only.
// Please, use the sort package of Go's Standard library: https://pkg.go.dev/sort

// Quicksort sorts the slice `vals` with the
// quicksort algorithm.
// Time: O(nlogn)
// Space: O(logn)
func Quicksort(vals []int) {
	if len(vals) < 2 {
		return
	}

	// Pick a pivot (random)
	// and swap it with the value at the last index
	pivot := rand.Int() % len(vals)
	vals[pivot], vals[len(vals)-1] = vals[len(vals)-1], vals[pivot]
	pivot = len(vals) - 1

	// Pile elements smaller than the pivot on the left
	lastSmaller := 0
	for idx, val := range vals {
		if val < vals[pivot] {
			vals[idx], vals[lastSmaller] = vals[lastSmaller], vals[idx]
			lastSmaller++
		}
	}

	// Place the pivot after the last smaller element
	vals[lastSmaller], vals[pivot] = vals[pivot], vals[lastSmaller]

	// Go down the rabbit hole
	Quicksort(vals[:lastSmaller])
	Quicksort(vals[lastSmaller+1:])
}