How Go Sorts: pdqsort, Pattern-Breaking and the O(n²) Guard

TL;DR: Go does not use sort.Slice’s old quicksort any more. Since Go 1.19 every sort in the standard library runs pdqsort — a pattern-defeating quicksort that sniffs out already-sorted input, recognises reverse-sorted input, breaks adversarial patterns with a seeded xorshift, and keeps a limit counter of bad pivots so it can bail out to heapsort before it ever degrades to O(n²).

Sorting is the most-executed algorithm in most programs, and the difference between a good sort and a bad one is measured in the whole application. Go’s standard library takes sorting seriously enough that it did the thing every other language runtime eventually does: it replaced a textbook quicksort with a much better one.

This is a walk through how it works, based on reading the Go source tree (Go 1.28 development tree).

The three entry points, and why they differ

Go offers three ways to sort a slice, and they are not the same code path:

go
// src/sort/sort.go:50
func Sort(data Interface) {
	n := data.Len()
	if n <= 1 {
		return
	}
	limit := bits.Len(uint(n))
	pdqsort(data, 0, n, limit)
}

go
// src/sort/slice.go:24
func Slice(x any, less func(i, j int) bool) {
	rv := reflectlite.ValueOf(x)
	swap := reflectlite.Swapper(x)
	length := rv.Len()
	limit := bits.Len(uint(length))
	pdqsort_func(lessSwap{less, swap}, 0, length, limit)
}

go
// src/slices/sort.go:16
func Sort[S ~[]E, E cmp.Ordered](x S) {
	n := len(x)
	pdqsortOrdered(x, 0, n, bits.Len(uint(n)))
}

All three call the same algorithm, but with three different plumbing mechanisms:

Entry point	Comparison	Swap	Extra cost
`sort.Sort`	interface method call	interface method call	dynamic dispatch on every compare
`sort.Slice`	`less` closure	`reflectlite.Swapper`	reflection-backed swap
`slices.Sort` / `slices.SortFunc`	monomorphised	monomorphised	none — generic, inlined

sort.Sort is the old interface-based API and pays a virtual call for every comparison and every swap. sort.Slice avoids the interface but has to rebuild a swapper out of reflectlite, which is reflection wearing a hat. slices.Sort is a generic function: the compiler specialises it for each element type, so data.Less(i, j) becomes a direct x[i] < x[j] with no interface, no closure, no reflection.

That is the whole reason slices.Sort beats sort.Slice by a large margin on small-to-medium slices: it is not a better algorithm, it is the same algorithm with the dispatch cost removed. If you are sorting []int in a hot loop, use slices.Sort.

pdqsort itself

The core loop, from the generated variant in src/sort/zsortfunc.go:

go
// src/sort/zsortfunc.go:61
func pdqsort_func(data lessSwap, a, b, limit int) {
	const maxInsertion = 12

	var (
		wasBalanced    = true // whether the last partitioning was reasonably balanced
		wasPartitioned = true // whether the slice was already partitioned
	)

	for {
		length := b - a

		if length <= maxInsertion {
			insertionSort_func(data, a, b)
			return
		}

		// Fall back to heapsort if too many bad choices were made.
		if limit == 0 {
			heapSort_func(data, a, b)
			return
		}

		// If the last partitioning was imbalanced, we need to breaking patterns.
		if !wasBalanced {
			breakPatterns_func(data, a, b)
			limit--
		}

		pivot, hint := choosePivot_func(data, a, b)
		if hint == decreasingHint {
			reverseRange_func(data, a, b)
			// The chosen pivot was pivot-a elements after the start of the array.
			// After reversing it is pivot-a elements before the end of the array.
			// The idea came from Rust's implementation.
			pivot = (b - 1) - (pivot - a)
			hint = increasingHint
		}

		// The slice is likely already sorted.
		if wasBalanced && wasPartitioned && hint == increasingHint {
			if partialInsertionSort_func(data, a, b) {
				return
			}
		}

		// Probably the slice contains many duplicate elements, partition the slice into
		// elements equal to and elements greater than the pivot.
		if a > 0 && !data.Less(a-1, pivot) {
			mid := partitionEqual_func(data, a, b, pivot)
			a = mid
			continue
		}

		mid, alreadyPartitioned := partition_func(data, a, b, pivot)
		wasPartitioned = alreadyPartitioned

		leftLen, rightLen := mid-a, b-mid
		balanceThreshold := length / 8
		if leftLen < rightLen {
			wasBalanced = leftLen >= balanceThreshold
			pdqsort_func(data, a, mid, limit)
			a = mid + 1
		} else {
			wasBalanced = rightLen >= balanceThreshold
			pdqsort_func(data, mid+1, b, limit)
			b = mid
		}
	}
}

Four ideas are packed into that loop, and they are the whole reason pdqsort beats a plain quicksort on real data:

text
        pdqsort(data, a, b, limit)
                 |
                 v
    +---------------------------+
    | length <= 12 ?            |--yes--> insertion sort (O(n^2), but n <= 12)
    +---------------------------+
                 | no
                 v
    +---------------------------+
    | limit == 0 ?              |--yes--> heapsort (O(n log n), worst case)
    +---------------------------+
                 | no
                 v
    +---------------------------+
    | !wasBalanced ?            |--yes--> breakPatterns (3 swaps)
    |                           |          limit--
    +---------------------------+
                 |
                 v
    +---------------------------+
    | choosePivot -> hint       |
    |  increasing? reverse?     |
    +---------------------------+
        |              |
        | decreasing   | increasing (and balanced & partitioned)
        v              v
   reverseRange   partialInsertionSort --> done in O(n)
        |
        v
  +----------------------------+
  | a-1 not < pivot ?         |--yes--> partitionEqual (many duplicates)
  +----------------------------+
        |
        v
  +----------------------------+
  | partition -> mid          |
  | recurse into the smaller  |
  | side, loop on the larger  |
  +----------------------------+

Small slices get insertion sort (≤ 12 elements). Insertion sort on 12 elements is a handful of comparisons and it is branch-predictable and cache-friendly. Partitioning 12 elements would cost more than sorting them.
A limit budget of bad pivots, with heapsort as the escape hatch.
Sortedness and reverse-sortedness are detected for free and handled in O(n) instead of O(n log n).
Runs of equal elements get a three-way partition so that a slice of a million identical strings does not degenerate.

The pivot, and how sortedness comes for free

The pivot chooser is the cleverest part:

go
// src/sort/zsortfunc.go:261
func choosePivot_func(data lessSwap, a, b int) (pivot int, hint sortedHint) {
	const (
		shortestNinther = 50
		maxSwaps        = 4 * 3
	)

	l := b - a

	var (
		swaps int
		i     = a + l/4*1
		j     = a + l/4*2
		k     = a + l/4*3
	)

	if l >= 8 {
		if l >= shortestNinther {
			// Tukey ninther method, the idea came from Rust's implementation.
			i = medianAdjacent_func(data, i, &swaps)
			j = medianAdjacent_func(data, j, &swaps)
			k = medianAdjacent_func(data, k, &swaps)
		}
		// Find the median among i, j, k and stores it into j.
		j = median_func(data, i, j, k, &swaps)
	}

	switch swaps {
	case 0:
		return j, increasingHint
	case maxSwaps:
		return j, decreasingHint
	default:
		return j, unknownHint
	}
}

The pivot is chosen at three quartiles of the slice (l/4, l/2, 3l/4), and for slices of 50 elements or more it uses Tukey’s ninther: take the median of each of three overlapping triples of adjacent elements, then take the median of those three medians. That is much more resistant to a bad adversarial arrangement than a plain median-of-three, because it samples nine elements spread across the slice rather than three.

But the real trick is the swaps counter. The median-of-three routine (median_func → order2_func) has to swap elements as it compares them to sort the three candidates into order. The number of swaps it performed is a free, exact signal about the shape of the input:

Zero swaps means the sampled elements were already in increasing order. For a random slice that is a 1-in-6 coincidence; for a sorted slice it is guaranteed. Hence increasingHint.
The maximum possible number of swaps means every sampled pair was inverted, i.e. the data is descending. Hence decreasingHint.
Anything in between: unknownHint.

The maximum is 4*3 = 12 because the ninther path performs twelve orderings (three medians of three adjacent elements, plus one median of the three medians). Note the consequence: only slices of 50 elements or more can reach the full twelve, so the reverse-sorted fast path only kicks in for larger slices. For lengths between 13 and 49 the ceiling is three swaps, and a descending slice is reported as unknownHint.

So Go’s sort knows it has been handed a sorted slice, without comparing the slice to itself. Sorting an already-sorted million-element slice then costs one O(n) pass to detect the shape plus one O(n) pass to reverse it (in the decreasing case) or a partial insertion sort (in the increasing case), instead of the full O(n log n) quicksort.

medianAdjacent_func is worth a look, because it is where the “ninther” actually happens:

go
// src/sort/zsortfunc.go:315
func medianAdjacent_func(data lessSwap, a int, swaps *int) int {
	return median_func(data, a-1, a, a+1, swaps)
}

The median of the adjacent elements around each quartile — so the three ninther medians are drawn from the neighborhoods of l/4, l/2 and 3l/4.

The already-sorted fast path

When the hint says “increasing” and the previous partition was already balanced and already partitioned, Go tries partialInsertionSort_func:

go
// src/sort/zsortfunc.go:195
func partialInsertionSort_func(data lessSwap, a, b int) bool {
	const (
		maxSteps         = 5  // maximum number of adjacent out-of-order pairs that will get shifted
		shortestShifting = 50 // don't shift any elements on short arrays
	)
	i := a + 1
	for j := 0; j < maxSteps; j++ {
		for i < b && !data.Less(i, i-1) {
			i++
		}

		if i == b {
			return true
		}

		if b-a < shortestShifting {
			return false
		}

		data.Swap(i, i-1)

		// Shift the smaller one to the left.
		if i-a >= 2 {
			for j := i - 1; j >= 1; j-- {
				if !data.Less(j, j-1) {
					break
				}
				data.Swap(j, j-1)
			}
		}
		// Shift the greater one to the right.
		if b-i >= 2 {
			for j := i + 1; j < b; j++ {
				if !data.Less(j, j-1) {
					break
				}
				data.Swap(j, j-1)
			}
		}
	}
	return false
}

This is a bail-out-friendly insertion sort. It scans forward looking for the first out-of-order adjacent pair. If it never finds one, the slice is sorted and it returns true — the whole sort is done, in one linear scan with no swaps at all. If it does find one, it shifts that element into place (with the smaller element sliding left and the greater one sliding right) and then keeps looking, but only for maxSteps = 5 such dislocations. If the slice turns out to be only nearly sorted, this routine gives up quickly and lets the normal quicksort path take over.

The shortestShifting = 50 guard means it will not even attempt the shifting on short arrays — the shift is O(n) and not worth it for a slice that is going to be insertion-sorted anyway.

Breaking patterns

The classic quicksort killer is a pre-arranged input where every pivot choice lands in the worst possible place. pdqsort’s answer is to notice imbalanced partitions and then scramble the data:

go
// src/sort/zsortfunc.go:240
func breakPatterns_func(data lessSwap, a, b int) {
	length := b - a
	if length >= 8 {
		random := xorshift(length)
		modulus := nextPowerOfTwo(length)

		for idx := a + (length/4)*2 - 1; idx <= a+(length/4)*2+1; idx++ {
			other := int(uint(random.Next()) & (modulus - 1))
			if other >= length {
				other -= length
			}
			data.Swap(idx, a+other)
		}
	}
}

Three elements — the ones straddling the midpoint of the slice — get swapped with three elements chosen at random. That is enough to destroy any locally-sorted structure an adversary could have built, while costing only three swaps.

The random source is a xorshift generator, and it is seeded with the slice length:

go
// src/sort/sort.go:67
// xorshift paper: https://www.jstatsoft.org/article/view/v008i14/xorshift.pdf
type xorshift uint64

func (r *xorshift) Next() uint64 {
	*r ^= *r << 13
	*r ^= *r >> 7
	*r ^= *r << 17
	return uint64(*r)
}

That is a deliberate choice and worth understanding. The generator is deterministic: the same length always produces the same permutation of positions. So Go’s sort has no run-to-run variability, which means a sort that occasionally misbehaves will misbehave the same way every time — good for debugging, and it means the function stays pure. It also means an adversary who knows the algorithm cannot do worse than the algorithm already handles.

Note also the modulus trick: nextPowerOfTwo(length) gives a power of two, so random.Next() & (modulus - 1) is a cheap mask instead of a division. If the masked value lands past the end of the slice it is folded back by subtracting the length. It is not a perfectly uniform distribution, but it does not need to be — it just needs to be uncorrelated with the input.

The O(n²) guard

The limit parameter is the safety net, and it is where the worst case is capped:

go
// src/sort/sort.go:55
	limit := bits.Len(uint(n))

bits.Len(uint(n)) is roughly log2(n) + 1. That is the number of bad pivots the sort is allowed to choose before it gives up. Each time a partition comes back badly imbalanced (wasBalanced becomes false), the sort calls breakPatterns_func and decrements limit. When limit hits zero:

go
// src/sort/zsortfunc.go:77
		// Fall back to heapsort if too many bad choices were made.
		if limit == 0 {
			heapSort_func(data, a, b)
			return
		}

Heapsort is O(n log n) with a bad constant factor — it does more swaps than quicksort and has terrible cache behaviour — but it cannot degrade. So the sort’s worst case is O(n log n) even for a deliberately hostile input, and the O(n²) behaviour that plagues naive quicksorts simply cannot happen.

The imbalance test itself is deliberately loose:

go
// src/sort/zsortfunc.go:117
		leftLen, rightLen := mid-a, b-mid
		balanceThreshold := length / 8
		if leftLen < rightLen {
			wasBalanced = leftLen >= balanceThreshold
			pdqsort_func(data, a, mid, limit)
			a = mid + 1
		} else {
			wasBalanced = rightLen >= balanceThreshold
			pdqsort_func(data, mid+1, b, limit)
			b = mid
		}

A partition is “balanced” if the smaller side is at least length/8. A perfectly balanced split gives length/2, so there is a lot of slack before a partition counts as bad. Only genuinely lopsided splits (worse than 7:1) burn a unit of the budget.

Duplicates get their own partition

One more case worth calling out: a slice containing many equal elements. Standard quicksort handles that badly, because equal elements all pile onto one side of the pivot and the recursion degenerates. Go checks for it:

go
// src/sort/zsortfunc.go:106
		// Probably the slice contains many duplicate elements, partition the slice into
		// elements equal to and elements greater than the pivot.
		if a > 0 && !data.Less(a-1, pivot) {
			mid := partitionEqual_func(data, a, b, pivot)
			a = mid
			continue
		}

If the element just before the current range is not less than the pivot, the range is probably all-equal-or-greater, and partitionEqual_func splits it into “equal to the pivot” followed by “greater than the pivot”. The equal run is then skipped entirely. Sorting a million copies of the same string degenerates to a single partition pass instead of a chain of n-deep recursion.

How the pieces are generated

One last piece of trivia that explains why there are three near-identical files. src/sort/zsortfunc.go starts with:

go
// src/sort/zsortfunc.go:1
// Code generated by gen_sort_variants.go; DO NOT EDIT.

The sort implementation is a template in src/sort/gen_sort_variants.go that is expanded into four variants at build time:

File	Variant	Used by
`src/sort/zsortinterface.go`	`Interface` methods	`sort.Sort`, `sort.Stable`
`src/sort/zsortfunc.go`	pair of `func` values	`sort.Slice`
`src/slices/zsortanyfunc.go`	generic + `cmp` func	`slices.SortFunc`
`src/slices/zsortordered.go`	generic + `cmp.Ordered`	`slices.Sort`

The last one is the reason slices.Sort is fast: because E is constrained to cmp.Ordered, the compiler knows the comparison is < on an ordered type and can inline it completely.

Trade-offs

What pdqsort buys: worst-case O(n log n) instead of O(n²); O(n) on already-sorted or reverse-sorted input; near-O(n) on nearly-sorted input; robustness against adversarial patterns; and no allocation at all (it is in-place, with O(log n) recursion depth).

What it costs:

It is not stable. Equal elements may be reordered. If you need stability, sort.Stable and slices.SortStableFunc use a completely different algorithm (an in-place merge sort built on symMerge and block rotations), not pdqsort.
The heapsort fallback is slow when it fires. It is O(n log n) but with a constant factor several times worse than quicksort, and it does not benefit from the sortedness detection. In practice it essentially never fires unless the input is adversarial.
The sortedness heuristic is a heuristic. It samples three (or nine) elements. A slice that is sorted except in an unsampled region will be sorted by the ordinary quicksort path, not the fast one. That is fine — it just means the fast path is a bonus, not a guarantee.
sort.Sort and sort.Slice are slower than slices.Sort for the reasons above, not because of the algorithm.

Caveats

Your Less function must be a strict weak ordering. If it is not — if it is inconsistent, non-transitive, or changes its answer between calls — no sort implementation can save you. sort.Interface says so explicitly, and the pdqsort implementation is no more forgiving than quicksort was.

Sorting a []interface{} with a comparison function that type-asserts can panic. The generic slices.SortFunc is happy with any E, but the comparison function still has to handle every element you hand it.

NaN breaks the ordering. slices.Sort orders NaN before other values (documented behaviour), but a hand-rolled Less using < on floats will not, and will produce a “sorted” slice that is not sorted by any consistent order. sort.Float64Slice handles NaN explicitly.

The generic instantiation cost. slices.Sort is generic, so each distinct element type gets its own compiled copy of the whole sort. For a program with dozens of distinct slice types that is real code size. The interface-based sort.Sort compiles once.

sort.Slice uses reflectlite.Swapper, which means it works on any slice but pays reflection costs per swap, and it panics on a non-slice argument.

Wrapping up

The one thing to remember: Go sorts with pdqsort, and its two most impressive tricks are free — the number of swaps performed while choosing a pivot tells you whether the input is sorted or reverse-sorted, and a bits.Len(n) budget of bad pivots guarantees the heapsort fallback kicks in before anything can degenerate to O(n²).

The part people get wrong: believing the sort is slow because of the algorithm. sort.Sort and sort.Slice are the same pdqsort as slices.Sort; they just pay an interface call or a reflection call on every comparison and every swap. Switching to slices.Sort is usually a bigger win than any algorithmic tweak you could make yourself.

What to go do about it: replace sort.Slice with slices.SortFunc (or slices.Sort for ordered types) in your hot paths, and profile a sort of already-sorted data to see the pdqsort fast path light up. If you need stable ordering, do not reach for slices.SortStableFunc blindly — it is a different algorithm with different asymptotics for equal elements.