djbsort is a software library for sorting arrays of integers or floating-point numbers. It provides the following features:

• Speed: djbsort established speed records for in-memory sorting when it was introduced, and remains competitive with newer sorting libraries.

• Security: djbsort is designed to be safe for cryptographic contexts.

• Verification: djbsort includes tools to automatically verify correctness.

These features are not separate options: there is a single sorting function that is simultaneously fast, secure, and verified.

The current release of djbsort has the following limitations:

• It sorts only signed 32-bit integers (int32), unsigned 32-bit integers (uint32), and 32-bit floating-point numbers (float32). However, the underlying techniques can easily be adapted to integers and floating-point numbers of other sizes (e.g., 64 bits). The techniques can also, with slightly more effort, permute fixed-size records or pointers to variable-size records along with the keys being sorted.

• It requires the array to fit into RAM (plus swap space). However, the underlying techniques can easily be adapted to larger arrays, such as arrays stored on disk. The data-access pattern is quite regular, and standard techniques to further reduce disk accesses are applicable.

• It sorts an array using one core on one machine, so the latency is suboptimal for large arrays. However, the underlying techniques can easily be parallelized across cores and across machines.

• The speed is only for CPUs with the AVX2 instruction set (e.g., Intel Haswell). However, the underlying optimization techniques can easily be ported to other CPUs.

• The verification has been tested for code produced by only a few compilers, and is likely to need changes to handle other compilers. It is possible that the C code has portability problems that damage correctness: for example, perhaps the C code triggers compiler bugs on some platforms.

• The verification has been applied only to the int32 software.

• The verification does not check memory safety.

• The verification runs separately for each array size, and becomes slower as the array size increases. On the other hand, this verification covers the specific array sizes used in cryptography.

Credits

The djbsort author is Daniel J. Bernstein.

djbsort builds upon results from the following paper: Daniel J. Bernstein, Chitchanok Chuengsatiansup, Tanja Lange, Christine van Vredendaal, "NTRU Prime: reducing attack surface at low cost", Selected Areas in Cryptography 2017. The NTRU Prime paper explained how to make constant-time sorting software run faster than Intel's sorting software on Intel CPUs, and demonstrated this with a software release in 2017. djbsort includes verification and provides another 3x speedup.