An in-place radix sorting algorithm designed for efficiently sorting uniformly distributed 64-bit integers stored as arrays or in block-based array format. Our main sorting algorithm combines an in-place most significant bit (MSB) radix sort, following the IPS²Ra approach, with a base sorting algorithm for small buckets. The radix sort partitions the input into buckets by processing 8 bits at a time and recursively sorts each bucket.
For buckets smaller than a threshold, the algorithm switches to Robin Hood sorting, which uses a temporary buffer larger than the bucket to map elements directly to their target positions. If a position is already occupied, the element is placed further ahead. After all elements are placed, the buffer is compacted and written back to the original data structure.
In addition to our main algorithm, we have also implemented a strictly in-place variant, i.e., not only requiring sublinear space but also constant space. This repository also includes re-implementations of Ska Sort and American Flag Sort for comparison and benchmarking purposes.
The build requirements are a Linux environment, a C++20 compiler (GCC/Clang), CMake (v3.15+) and a build system (Ninja, GNU Make, etc.). Use the following steps below to build it:
# Fetch a copy if not already present...
git clone https://github.com/dsalwasser/sort.git
cd sort
# ...and build it
cmake --preset=linux
cmake --build build --preset=linux --parallelIf you're using Nix flakes, you can install or run it directly from its GitHub repository:
nix run github:dsalwasser/sort -- --input <input_file> --output <output_file>We provide the sort application to sort 64-bit integers stored in a text or binary file and to write the corresponding sorted integers to an output file. To use this application, first compile it by following the above steps and then run:
./build/linux/app/sort --input <input_file> --output <output_file>For more information use ./build/linux/app/sort --help.
This project is licensed under the MIT License.