Go Quickselect and Sorting: slices.Sort to Top-K in O(n)

Sorting a slice in Go is a one-liner: slices.Sort(nums). But many real questions don't need a fully sorted slice. "What's the 95th-percentile latency?" or "Which 10 products sold most?" only need one position or the top k, and Go quickselect answers those in O(n) average time instead of O(n log n). Go's standard library has no built-in quickselect, so it's worth knowing how to write one.

This guide covers the everyday tools (sort, slices, multi-key sorts, frequency maps), then builds Lomuto partition, quicksort and quickselect from scratch and uses them for the classic top-k problems.

Sorting slices in Go: sort vs slices

Go has two sorting packages. sort is the original. slices arrived in Go 1.21 with generics and is now the one to reach for. Both use pattern-defeating quicksort (pdqsort) under the hood.

nums := []int{5, 2, 9, 1, 5, 6}
slices.Sort(nums)  // [1 2 5 5 6 9]
sort.Ints(nums)    // same result, older API

names := []string{"mango", "Apple", "banana"}
slices.Sort(names) // [Apple banana mango]

slices.SortFunc is usually faster than sort.Slice because it works on typed values instead of going through reflection-based swapping, and the comparator is easier to read.

Sorting strings

String comparison in Go is byte-wise, so uppercase letters sort before lowercase: "Apple" < "banana" but also "Zebra" < "apple". For a case-insensitive order, compare lowered copies:

slices.SortFunc(names, func(a, b string) int {
	return strings.Compare(strings.ToLower(a), strings.ToLower(b))
})

To sort the characters inside a string, for example to check for anagrams, convert to []rune first so multi-byte characters stay intact:

func sortString(s string) string {
	r := []rune(s)
	slices.Sort(r)
	return string(r)
}

sortString("golang") // "agglno"

Sorting []byte instead would break any character outside ASCII. Strings, bytes and runes in Go explains why.

Sorting structs by several keys

cmp.Or (Go 1.22) returns the first non-zero value, which makes multi-key comparators short:

type Player struct {
	Name  string
	Score int
}

slices.SortFunc(players, func(a, b Player) int {
	return cmp.Or(
		cmp.Compare(b.Score, a.Score),  // higher score first
		strings.Compare(a.Name, b.Name), // then by name
	)
})

Swapping a and b in cmp.Compare gives descending order. To reverse an already sorted slice, use slices.Reverse.

Counting frequencies with a map

Counting how often each value appears is the first step of many ranking problems. A map[T]int does it in one pass:

words := strings.Fields("the cat and the dog and the bird")

counts := make(map[string]int)
for _, w := range words {
	counts[w]++ // missing keys start at zero
}

keys := make([]string, 0, len(counts))
for w := range counts {
	keys = append(keys, w)
}
slices.SortFunc(keys, func(a, b string) int {
	return cmp.Or(cmp.Compare(counts[b], counts[a]), strings.Compare(a, b))
})
// the 3, and 2, bird 1, cat 1, dog 1

Map iteration order is random in Go, so always sort the keys when output order matters. See Go slices, maps and pointers for more on how maps behave.

This approach costs O(n) to count plus O(m log m) to sort the m distinct keys. If you only need the top few, quickselect can remove the sort.

Lomuto partition: the core of quicksort

Quicksort and quickselect share one building block: partition. Pick a pivot, then rearrange the slice so everything smaller than the pivot is on its left and everything else is on its right. The pivot ends up in its final sorted position.

The Lomuto scheme is the easiest to get right. It keeps one index i as the boundary of the "smaller than pivot" region and scans with j:

// partition rearranges a[lo..hi] around a random pivot and returns
// the pivot's final index p: a[lo..p-1] < a[p] <= a[p+1..hi].
func partition(a []int, lo, hi int) int {
	p := lo + rand.IntN(hi-lo+1) // math/rand/v2
	a[p], a[hi] = a[hi], a[p]    // move the pivot to the end
	pivot := a[hi]

	i := lo // a[lo..i-1] holds elements smaller than pivot
	for j := lo; j < hi; j++ {
		if a[j] < pivot {
			a[i], a[j] = a[j], a[i]
			i++
		}
	}
	a[i], a[hi] = a[hi], a[i] // place the pivot between the two parts
	return i
}

A short trace with pivot 4 on [7 2 9 1 4]:

Why the pivot is random

The textbook version always uses the last element as the pivot. On input that's already sorted, that pivot is the maximum every time, each partition removes only one element, and the running time becomes O(n²). A random pivot makes that worst case extremely unlikely for any input.

math/rand/v2 (Go 1.22) provides rand.IntN(n), which returns a number in [0, n). The older math/rand has the same function spelled rand.Intn(n). Since Go 1.20 both are seeded automatically, so you no longer call rand.Seed.

Quicksort in Go

With partition in place, quicksort is three lines of logic: partition, then sort each side.

func quickSort(a []int, lo, hi int) {
	if lo >= hi {
		return
	}
	p := partition(a, lo, hi)
	quickSort(a, lo, p-1)
	quickSort(a, p+1, hi)
}

quickSort(nums, 0, len(nums)-1)

Writing quicksort yourself is a good exercise, but in production use slices.Sort, which handles duplicates and adversarial inputs far better. One known weakness of Lomuto in particular: when many elements are equal, the partitions become lopsided and performance drops toward O(n²). A three-way partition (less, equal, greater) fixes that.

Go quickselect: find the k-th element in O(n)

Quicksort recurses into both sides of the pivot. Quickselect notices that after one partition you know exactly which side the k-th element is on, so it only continues into that side.

// quickSelect returns the k-th smallest element (0-based).
// It reorders a in place.
func quickSelect(a []int, k int) int {
	lo, hi := 0, len(a)-1
	for lo < hi {
		p := partition(a, lo, hi)
		switch {
		case p == k:
			return a[k]
		case p < k:
			lo = p + 1 // answer is on the right
		default:
			hi = p - 1 // answer is on the left
		}
	}
	return a[k]
}

On average each partition halves the remaining range, so the total work is roughly n + n/2 + n/4 + … ≈ 2n, which is O(n). The worst case is still O(n²), but with a random pivot it's very unlikely.

The k-th largest element is the (len-k)-th smallest, which solves the well-known LeetCode "Kth Largest Element in an Array" problem:

func findKthLargest(nums []int, k int) int {
	a := slices.Clone(nums) // don't reorder the caller's slice
	return quickSelect(a, len(a)-k)
}

findKthLargest([]int{3, 2, 1, 5, 6, 4}, 2) // 5

Top-k frequent elements with quickselect

Combining the frequency map with quickselect solves "Top K Frequent Elements" without sorting all the keys. A generic version of the same algorithm takes a less function:

// selectBy reorders a so that a[k] is the element that would be at index k
// if a were sorted by less, with every element before it not greater.
func selectBy[T any](a []T, k int, less func(x, y T) bool) {
	lo, hi := 0, len(a)-1
	for lo < hi {
		p := lo + rand.IntN(hi-lo+1)
		a[p], a[hi] = a[hi], a[p]
		i := lo
		for j := lo; j < hi; j++ {
			if less(a[j], a[hi]) {
				a[i], a[j] = a[j], a[i]
				i++
			}
		}
		a[i], a[hi] = a[hi], a[i]
		switch {
		case i == k:
			return
		case i < k:
			lo = i + 1
		default:
			hi = i - 1
		}
	}
}

func topKFrequent(nums []int, k int) []int {
	freq := make(map[int]int)
	for _, n := range nums {
		freq[n]++
	}
	keys := make([]int, 0, len(freq))
	for n := range freq {
		keys = append(keys, n)
	}
	if k >= len(keys) {
		return keys
	}
	// "less" means "more frequent", so the k most frequent land in keys[:k].
	selectBy(keys, k-1, func(x, y int) bool { return freq[x] > freq[y] })
	return keys[:k]
}

topKFrequent([]int{1, 1, 1, 2, 2, 3}, 2) // [1 2] in some order

The result is the top k, but not sorted among themselves. If you need them ranked, sort just those k elements afterward, which costs O(k log k).

Big-O comparison

A deterministic O(n) worst case exists (median of medians), but its constant factors make it slower than random-pivot quickselect in practice.

Big-O doesn't predict wall-clock time for small inputs. If the choice matters, benchmark it and profile with pprof.

FAQ

Is sort.Slice stable in Go?

No. sort.Slice and slices.SortFunc may reorder equal elements. Use sort.SliceStable or slices.SortStableFunc when the original order of ties must be kept.

What is the difference between sort.Slice and slices.SortFunc?

sort.Slice takes a less(i, j int) bool that works with indexes. slices.SortFunc takes a generic comparator on the values themselves, returning an int. slices.SortFunc is type-safe, easier to read and usually faster.

Does Go have a built-in quickselect?

No. The standard library has no equivalent of C++'s nth_element. You either sort and index, use container/heap, or write quickselect yourself as shown above.

Should I use quickselect or a heap for top k?

Use quickselect when the data is already in a slice you can reorder and you want the fastest average case. Use a heap of size k when data arrives as a stream, when you can't modify the input, or when you need guaranteed O(n log k).

Takeaways

• Use slices.Sort and slices.SortFunc for everyday sorting, with cmp.Or for multi-key orders.
• Sort []rune, not []byte, when rearranging characters.
• Count with a map, and sort the keys when order matters.
• Reach for quickselect when you need one position or an unordered top k, and pick the pivot at random.
• Measure before replacing the standard library sort with anything hand-written.

If your team needs help with performance-sensitive Go services, Vectorkub builds and reviews backend systems.