How Vectorized Quicksort Fills Every CPU Lane

The moment sorting stops looking serial

Picture a column of timestamps, prices, or sensor readings containing a million values. A normal sort appears to work like a patient clerk: compare one value, decide where it belongs, move to the next. Yet a modern central processing unit (CPU) contains registers designed to hold several values at once. The gap between those two facts is where vectorized Quicksort begins.

Google published an open-source implementation on June 2, 2022. Its headline result was roughly ten times the speed of C++ std::sort for the tested numeric arrays, while using one portable implementation across several modern CPU instruction sets. The important idea was not a radically different pivot formula. It was changing how the most expensive part of Quicksort handles data. (opensource.googleblog.com)

The old Quicksort story

Quicksort is a divide-and-conquer algorithm, which means it breaks a large problem into smaller ones. It chooses a value called a pivot, then partitions the array so values below the pivot move toward one side and the remaining values move toward the other. The algorithm repeats that process until the pieces are small enough to finish with a compact sorting routine.

That partition step sounds tidy on paper. In a traditional implementation, though, the CPU repeatedly loads one element, compares it with the pivot, branches based on the result, and moves a pointer. Do that for every value in a large array and the control flow becomes the bottleneck. Google’s implementation focuses on this partitioning work because it accounts for much of Quicksort’s running time.

The design fits especially well with columnar data, a layout where one array stores only one kind of value, such as all prices or all timestamps. Because those values sit next to one another in memory, the CPU can load a wide block without chasing pointers through a collection of larger records.

SIMD turns one comparison into many

SIMD, short for single instruction, multiple data, lets one CPU instruction perform the same operation on several independent values. A vector register is a small storage area inside the processor, and its individual positions are commonly called lanes. With AVX-512, for example, a register can hold sixteen 32-bit floating-point values; Arm NEON can hold four of those values in a 128-bit vector.

SIMD is not the same as multithreading. We are not starting sixteen threads or adding sixteen CPU cores. One core is executing one instruction over several lanes, like comparing a whole row of mailbox numbers with the same reference number instead of checking each mailbox separately.

How does vectorized Quicksort work?

Suppose the pivot is 50. The algorithm loads a vector of values, compares every lane with 50, and receives a mask: one yes-or-no bit for each lane. That mask records which values belong in the lower partition.

The central operation can be pictured like this:

values = load_vector(input)
mask = values < pivot
compress_store(left_cursor, values, mask)
compress_store(right_cursor, values, inverse(mask))

This is conceptual pseudocode rather than a complete implementation. The key instruction is compress-store. It takes the lanes selected by a mask and writes them next to one another in memory, removing the gaps created by unselected lanes. The algorithm then repeats the operation with the inverse mask for values on the other side of the pivot.

That move turns a scattered, branch-heavy decision into two dense writes. Some processors provide compress-store directly. Others do not. The portable implementation can emulate the same behavior with permute operations, which rearrange lanes according to a pattern. This distinction matters because x86 AVX-512, Arm SVE, and RISC-V V expose different capabilities, while older x86 AVX2 lacks a native compress-store instruction. (opensource.googleblog.com)

Portability without six separate codebases

An instruction set architecture, or ISA, is the collection of machine operations exposed by a processor family. Writing SIMD code directly against an ISA usually means using low-level functions called intrinsics, and each family brings its own names, vector widths, and edge cases.

Google built the sorter on Highway, a C++ library that provides portable SIMD operations. Highway can choose the best available instruction set at runtime, so the application can use AVX2 on one machine, AVX-512 on another, or Arm instructions on a different system without maintaining a completely separate sorting algorithm for each target.

The 2022 announcement described the project as the first vectorized Quicksort portable across six instruction sets and three architectures. The accompanying paper reported a broader version supporting seven instruction sets across four platforms, including Arm SVE and RISC-V V, along with floating-point and 16- to 128-bit integer keys. That is the practical achievement behind the word portable: one algorithmic design, adapted by the library rather than rewritten from scratch for every processor.

Small arrays need a different trick

Wide vectors shine when there is a lot of data to feed them. Quicksort eventually produces smaller and smaller partitions, so the implementation needs a good strategy for the final few hundred elements too.

Here the project uses sorting networks. A sorting network is a fixed sequence of compare-and-exchange operations whose pattern does not depend on the input values. Because the sequence is predetermined, it can be arranged to work efficiently inside registers without the branching behavior of a general-purpose loop. The paper describes compact, transpose-free networks for small arrays, while the original announcement highlights a special case around 256 elements. (research.google)

This hybrid design is easy to miss. Vectorized Quicksort is not one giant SIMD loop. It is a collection of carefully matched pieces: fast partitioning for large regions, register-friendly networks for small ones, and pivot selection that avoids turning an awkward input into a disastrously unbalanced recursion tree.

What did the benchmark look like?

Google’s June 2022 measurements sorted one million 32-, 64-, or 128-bit values at 499, 471, and 466 megabytes per second on an Apple M1. On a 3 GHz Intel Skylake processor using AVX-512, the corresponding rates were 1123, 1119, and 1120 megabytes per second. On the same CPU with AVX2, the sorter reached 798 megabytes per second, compared with 58, 128, and 117 megabytes per second for the tested standard-library cases.

Those figures are architecture-specific measurements, not a promise that every array will see the same multiplier. Data type, compiler, memory behavior, input distribution, and the competing library all matter. Still, the results show why sorting can become interesting again when a single core can process data at roughly a gigabyte per second.

What using it looks like

As of September 2026, the current Highway source still exposes VQSort through its sorting contribution. A minimal call has the shape below:

#include <hwy/contrib/sort/vqsort.h>

hwy::VQSort(values, count, hwy::SortAscending);

Here, values represents a contiguous numeric array and count is the number of elements. The current interface dispatches to the best available instruction set and does not allocate memory for the sort. It is not stable, meaning equal keys are allowed to change their relative order. The header also recommends using it for arrays of at least 100 KiB, because the overhead of wide-vector machinery may not pay off for tiny inputs. (github.com)

Vectorized Quicksort is therefore not a universal replacement for every sorting call. Custom objects, complicated comparison functions, and small collections may need different trade-offs. Its sweet spot is large, contiguous collections of primitive values where the CPU can keep several lanes busy.

The deeper lesson is that this is not a new asymptotic trick. The familiar pivot-and-partition strategy remains. What changes is the unit of work: instead of treating one value as the natural amount of progress, the implementation treats a whole vector as one step. The research paper even showed how the sorter could fit inside a parallel sorting algorithm, demonstrating that SIMD and multiple CPU cores can complement one another. (research.google)

The algorithm is familiar. The machine’s idea of one piece of work is not.