Smart Sort

Smart Sort is a header-only C++20 library that uses parallel LSD radix sort for large vectors of 32-bit and 64-bit integers and floating-point values. It falls back to std::sort for unsupported types, custom comparators, oversized inputs, or when its temporary buffer cannot be allocated.

The project is currently an experimental 0.x release. The API may change before 1.0.

Performance highlight: in the latest local benchmark with 10 million random int32_t values, Smart Sort completed in 16.4 ms—about 2.4x faster than the fastest other tested implementation and 29.0x faster than sequential std::sort. Full results and limitations are shown below.

Requirements

• C++20 compiler
• CMake 3.20 or newer when using the provided CMake package
• A standard library implementation with std::barrier and std::thread

Tested by CI on Linux, macOS, and Windows.

Quick start

#include <smart_sort/sort.hpp>

#include <iostream>
#include <vector>

int main() {
    std::vector<int> values = {5, 2, 9, 1, 5, 6, 3};
    smart_sort::sort(values);

    for (int value : values) std::cout << value << ' ';
}

The original API remains available as Algorithms::Sorting::sort(values). When copying only Sorting.hpp into a project, include it directly with #include "Sorting.hpp".

Key extractor

struct Player {
    int id;
    std::uint32_t score;
};

std::vector<Player> players = load_players();
smart_sort::sort(players, [](const Player& player) noexcept {
    return player.score;
});

A 32-bit or 64-bit integer, float, or double key can use the radix path when the record type is suitable for the temporary buffer. Other key types use a comparison fallback. Mark non-throwing extractors noexcept to make them eligible for parallel radix sorting; potentially throwing extractors always use the comparison fallback so exceptions can propagate normally.

Comparator

smart_sort::sort(values, [](int lhs, int rhs) {
    return lhs > rhs;
});

Custom comparators are handled by std::sort, so their ordering semantics are preserved.

CMake integration

With FetchContent:

include(FetchContent)
FetchContent_Declare(
    smart_sort
    GIT_REPOSITORY https://github.com/Vo1ic/smart-sort.git
    GIT_TAG v0.1.0
)
FetchContent_MakeAvailable(smart_sort)

target_link_libraries(your_target PRIVATE smart_sort::smart_sort)

Or install and consume the package:

cmake -S . -B build -DSMART_SORT_BUILD_TESTS=OFF
cmake --install build --prefix /your/prefix

find_package(SmartSort CONFIG REQUIRED)
target_link_libraries(your_target PRIVATE smart_sort::smart_sort)

The repository also contains a Conan 2 recipe for local packaging:

conan create .

Ordering and limitations

• Default floating-point sorting places all NaNs after non-NaN values.
• Radix sorting needs an additional buffer approximately equal to the input size. Allocation failure causes a comparison-sort fallback before the input is modified.
• The accelerated path accepts at most INT_MAX elements; larger vectors use std::sort.
• The public API currently accepts std::vector. Iterator and range overloads are planned for a future release.
• The selection thresholds are heuristics and may not be optimal for every CPU or workload.
• No stability guarantee is part of the public API.

Tests

cmake -S . -B build -DSMART_SORT_BUILD_TESTS=ON
cmake --build build
ctest --test-dir build --output-on-failure

The suite covers random and adversarial distributions, sequential and parallel paths, signed and unsigned keys, floating-point edge cases, strings, custom comparators, and record key extractors.

Latest verification results

Local verification performed on 2026-07-16 on Arch Linux x86-64:

Check	Toolchain	Result
Release build and correctness suite	GCC 16.1.1, C++20	Passed
AddressSanitizer and UndefinedBehaviorSanitizer	Clang 22.1.8, C++20	Passed
ThreadSanitizer	Clang 22.1.8, C++20	Passed; no data races reported
Installed CMake package consumer	GCC 16.1.1, C++20	Built and executed successfully
Conan package and test_package	Conan 2.30.0, GCC 16, C++20	Created, linked, and executed successfully

The correctness suite includes parallel runs with 400,000 values for 32-bit and 64-bit signed and unsigned integers, random floating-point bit patterns, NaN ordering, narrow-range distributions, binary strings, custom comparators, and extracted record keys. Every result is validated against its documented ordering or std::sort.

Benchmarks

The benchmark reports CSV data and validates every sorted result:

cmake -S . -B build -DCMAKE_BUILD_TYPE=Release \
  -DSMART_SORT_BUILD_TESTS=OFF \
  -DSMART_SORT_BUILD_BENCHMARKS=ON
cmake --build build --config Release
./build/smart_sort_benchmark --size 10000000 --rounds 5

Benchmark results depend heavily on the CPU, compiler, optimization flags, standard library, input distribution, and available memory. Publish those details together with any performance numbers.

Latest performance results

Environment: AMD Ryzen 5 7500F (6 cores/12 threads), 32 GB RAM, Arch Linux x86-64, GCC 16.1.1, Boost 1.91.0, oneTBB 2023.0.0, C++20, CMake Release (-O3 -DNDEBUG). Each case sorts 10,000,000 int32_t values. The table reports the median of five rounds in milliseconds; lower is better.

Algorithm	Random	Sorted	Reversed	256 unique
std::sort	475.322	73.692	49.860	223.109
std::sort(std::execution::par)	60.711	4.516	14.201	40.063
Boost pdqsort	185.554	4.069	9.309	48.866
Boost spreadsort	214.630	2.048	77.803	45.069
Boost block_indirect_sort	39.473	2.062	2.909	15.953
Smart Sort	16.412	15.607	15.586	8.267

On random data, Smart Sort was 29.0x faster than sequential std::sort, 3.7x faster than parallel std::sort, and 2.4x faster than the next-fastest tested implementation. With 256 unique values it was 27.0x faster than std::sort and 1.9x faster than the next-fastest implementation. Adaptive comparison sorts were substantially faster on already sorted and reversed inputs.

Input copying and result validation are outside the timed region. Internal allocation, thread creation, and all sorting work are included. Algorithm order is shuffled each round, every algorithm receives identical input, and every result is checked with std::is_sorted. A second independent run produced consistent random-data results (16.3 ms for Smart Sort and 39.4 ms for the next-fastest implementation). These are project-author measurements, not independent third-party results.

Contributing

Bug reports and pull requests are welcome. See CONTRIBUTING.md for the required checks.

Smart Sort is available under the MIT License.