Google has released open-source code for a vectorized Quicksort implementation that sorts arrays roughly ten times faster than the C++ standard library’s std::sort, according to the Google Open Source Blog.
The algorithm achieves this speedup by leveraging SIMD (Single Instruction Multiple Data) vector instructions, which perform operations on multiple independent elements in a single CPU instruction. For example, AVX-512 can operate on 16 float32 values simultaneously, while Arm NEON handles four at once.
The key innovation lies in accelerating the partitioning phase of Quicksort, which accounts for most CPU time during sorting. Modern instruction sets including Arm SVE, RISC-V V, and x86 AVX-512 include a “compress-store” instruction that efficiently partitions data based on a pivot value. For instruction sets like AVX2 that lack this feature, the implementation emulates it using permute instructions.
Unlike previous approaches, Google’s implementation is portable across six instruction sets spanning three architectures—Intel AVX2, Intel AVX-512, and Arm NEON—without requiring separate implementations for each platform. The code uses Highway’s portable SIMD functions to avoid reimplementing approximately 3,000 lines of C++ for each CPU architecture. It also supports a broader range of input sizes (16-128 bit) compared to prior work, which was limited to 32-bit integers.
Performance benchmarks show significant improvements across platforms. On Apple M1 (Arm NEON), the implementation achieves 499 MB/s for 32-bit numbers, 471 MB/s for 64-bit, and 466 MB/s for 128-bit numbers. On a 3 GHz Intel Skylake with AVX-512, speeds reach 1,123 MB/s, 1,119 MB/s, and 1,120 MB/s respectively. On AVX2, the implementation achieves 798 MB/s, compared to 699 MB/s for previous state-of-the-art AVX2-specific algorithms.
When compared to the standard library’s std::sort on the same Skylake CPU, the speedup ranges from 9x to 19x depending on numeric type. According to the blog post, AVX-512 is 1.4-1.6 times faster than AVX2 on the same hardware, despite using the same portable codebase.
The Apache2-licensed source code is available on Github, along with a detailed paper explaining the implementation and evaluation methodology.
Key facts
- Google’s vectorized Quicksort achieves approximately 10x speedup over C++ std::sort
- The implementation is portable across six instruction sets on three CPU architectures (Intel AVX2, AVX-512, and Arm NEON)
- Performance reaches up to 1,123 MB/s on Intel Skylake with AVX-512, compared to 58 MB/s for std::sort
- The algorithm uses SIMD vector instructions to accelerate the partitioning phase of Quicksort
- The code supports 16-128 bit inputs, broader than previous implementations limited to 32-bit integers