Pattern-Defeating Quicksort (pdqsort) in Go: Design, Implementation, and Performance

Sorting algorithms such as quicksort, heap sort, and insertion sort are well known, but modern languages often use hybrid unstable sorts that switch strategies based on data characteristics. The article introduces ByteDance’s language team’s work on integrating pdqsort—a pattern‑defeating quicksort—into Go 1.18 using generics, achieving 2×‑60× faster performance than the standard library in almost all scenarios.

pdqsort is a hybrid algorithm that combines quicksort, insertion sort, and heap sort. For small arrays (length ≤ MAX_INSERTION, set to 24 in Go tests) it uses insertion sort. If the quicksort partition is unbalanced and a limit counter reaches zero, it falls back to heap sort to guarantee O(n·log n) worst‑case complexity.

During normal operation the algorithm repeatedly executes the following steps: break patterns when the previous partition was unbalanced, choose a pivot using a multi‑stage median‑of‑medians strategy, optionally apply a partial insertion sort when the data appears nearly sorted, handle many duplicate elements with a special partitionEqual routine, and finally perform a standard partition that also detects already‑sorted sub‑arrays.

The pivot‑selection logic adapts to array length: for very short arrays a fixed pivot is used; for medium lengths the classic median‑of‑three is applied; for larger arrays Tukey’s ninther (median‑of‑medians of nine elements) provides a high‑quality approximate median. The algorithm also detects locally sorted or reverse‑sorted patterns and may reverse the whole array to improve locality.

In Go 1.18 the use of generics eliminates the overhead of sort.Interface , allowing the compiler to generate type‑specific code and yielding roughly a 2× speed improvement. Benchmarks show pdqsort outperforming Go’s original introsort‑like algorithm by 1‑30× on common patterns such as already sorted, nearly sorted, reverse sorted, or data with many duplicates.

Despite its advantages, pdqsort is not universally optimal; for mixed ascending/descending runs Python’s timsort can be faster. Nevertheless, pdqsort has become the dominant unstable sort in many industrial projects and has been merged into the Go runtime as the default unstable sort for Go 1.19 (generic version in exp/slices , non‑generic in sort ).

References include the original pdqsort paper (https://arxiv.org/pdf/2106.05123.pdf), the Rust and C++ Boost implementations, and the GitHub repository https://github.com/zhangyunhao116/pdqsort. The article also contains a brief appendix comparing various quicksort pivot strategies such as first‑element, median‑of‑three, median‑of‑medians, and Tukey’s ninther.