Google introduced a vector implementation of the Quicksort algorithm

Company Google has published the source code of a high-performance library for sorting data using vector processor instructions. The new Quicksort algorithm utilizes SIMD (Single Instruction, Multiple Data) capabilities to accelerate array processing.

In internal tests, the solution showed a speed increase of 9–19 times compared to the standard C++ std::sort library. When using AVX-512 instructions, the algorithm achieves a throughput of up to 1.1 GB/s, which significantly exceeds the performance of traditional implementations tied to specific processor architectures.

Developers focused on code portability, ensuring efficient operation on various hardware platforms. The library is optimized to minimize branching and effectively use cache memory, allowing for high operation density when sorting large amounts of data.

This release is part of Google's efforts to optimize low-level computational tasks. The use of vector calculations makes it possible to significantly reduce the load on the CPU when performing standard operations that are critical for the operation of databases and systems for processing large amounts of information.