A fast, header-only C++17 sorting library for numeric types

Algorithm      Random       Dense (0-100)    vs std::sort
─────────────────────────────────────────────────────────
std::sort      5,364 us     3,347 us         1.0x
tieredsort     1,494 us       159 us         3.6x - 21x

Highlights:

• 3.6x faster on random data
• 16-21x faster on dense/few-unique data
• 6.2x faster on Zipf distributions

tieredsort is a high-performance sorting algorithm that automatically selects the optimal sorting strategy based on your data characteristics. It achieves excellent performance for numeric types without requiring SIMD instructions.

#include "tieredsort.hpp"

std::vector<int> data = {5, 2, 8, 1, 9};
tiered::sort(data.begin(), data.end());  // That's it!

• 20 timed runs per seed, 3 warmup runs
• 5 different random seeds to avoid data bias
• Rotating algorithm order to avoid cache bias
• Reporting median with IQR (interquartile range)
• Compiled with GCC 13.1, -O3 -std=c++17 -march=native

All tests passed with 100% correctness:

• 159/159 unit tests (size scaling, edge cases, negative numbers, stability verification)
• 15/15 real-world patterns across 3 data sizes (10K, 100K, 1M)
• 10 random seeds tested for consistency
• Statistical significance verified (100 runs, p < 0.001)

tieredsort uses a 3-tier decision tree that analyzes your data and picks the optimal algorithm:

                           +-------------+
                           | tieredsort  |
                           +------+------+
                                  |
                    +-------------+-------------+
                    v                           |
            +---------------+                   |
            |  n < 256?     |---Yes---> std::sort (low overhead)
            +-------+-------+
                    | No
                    v
            +---------------+
            |   Pattern     |---Yes---> std::sort (O(n) for sorted)
            |   detected?   |
            +-------+-------+
                    | No
                    v
            +---------------+
            | Dense range?  |---Yes---> counting sort (O(n + range))
            | (range <= 2n) |
            +-------+-------+
                    | No
                    v
            +---------------+
            |    Default    |---------> radix sort (O(n))
            +---------------+

• Pattern check: 12 comparisons (head, middle, tail)
• Range sampling: 64 samples
• Total: ~100 CPU cycles = negligible

curl -O https://raw.githubusercontent.com/Cranot/tieredsort/main/include/tieredsort.hpp

include(FetchContent)
FetchContent_Declare(
  tieredsort
  GIT_REPOSITORY https://github.com/Cranot/tieredsort.git
  GIT_TAG main
)
FetchContent_MakeAvailable(tieredsort)

target_link_libraries(your_target PRIVATE tieredsort)

Just copy include/tieredsort.hpp to your project. That's it!

#include "tieredsort.hpp"
#include <vector>

int main() {
    std::vector<int> data = {5, 2, 8, 1, 9, 3, 7, 4, 6};

    tiered::sort(data.begin(), data.end());
    // data is now {1, 2, 3, 4, 5, 6, 7, 8, 9}

    return 0;
}

int arr[] = {5, 2, 8, 1, 9};
tiered::sort(arr, arr + 5);

std::vector<int> data(100000);
std::vector<int> buffer(100000);  // Reusable buffer

// Fill data...

// Sort without internal allocation
tiered::sort(data.begin(), data.end(), buffer.data());

// Sort structs by a numeric key - stability IS observable here
struct Student { std::string name; int32_t score; };
std::vector<Student> students = {...};

tiered::sort_by_key(students.begin(), students.end(),
    [](const Student& s) { return s.score; });
// Students with equal scores maintain their original order

Performance (vs std::stable_sort with comparator):

• Dense keys (ages 0-100, scores 0-1000): 3-6x faster
• Sparse keys (random 32-bit): ~1x (graceful fallback)

Uses counting sort directly on objects for dense ranges - O(n + range) with only 2 allocations.

// For primitives, stable_sort works but stability is NOT observable
// (equal values are indistinguishable - you can't tell which "85" came first)
std::vector<int> scores = {85, 90, 85, 92, 90};
tiered::stable_sort(scores.begin(), scores.end());
// Use sort_by_key() for objects where stability matters

tiered::sort(vec_int32.begin(), vec_int32.end());   // int32_t
tiered::sort(vec_uint32.begin(), vec_uint32.end()); // uint32_t
tiered::sort(vec_int64.begin(), vec_int64.end());   // int64_t
tiered::sort(vec_uint64.begin(), vec_uint64.end()); // uint64_t
tiered::sort(vec_float.begin(), vec_float.end());   // float
tiered::sort(vec_double.begin(), vec_double.end()); // double

¹ Key-Stable: sort_by_key() provides stable sorting for objects by a numeric key.

Note: vqsort requires AVX2/AVX-512 hardware. tieredsort works on any CPU.

• C++17 compiler (GCC 7+, Clang 5+, MSVC 2017+)
• No external dependencies
• No SIMD requirements

• Numeric types only: int32, int64, uint32, uint64, float, double
• Requires O(n) buffer: For radix sort (auto-allocated or user-provided)

Sort elements in range [first, last).

template<typename RandomIt>
void sort(RandomIt first, RandomIt last);

Sort elements using provided buffer (avoids internal allocation).

template<typename RandomIt>
void sort(RandomIt first, RandomIt last,
          typename std::iterator_traits<RandomIt>::value_type* buffer);

Sort objects by a numeric key with observable, verifiable stability. Objects with equal keys maintain their relative order.

template<typename RandomIt, typename KeyFunc>
void sort_by_key(RandomIt first, RandomIt last, KeyFunc key_func);
// key_func must return int32_t or uint32_t

Stable sort for primitives. Note: for primitive types (int, float, etc.), stability is maintained but not observable since equal values are indistinguishable. Use sort_by_key() for objects where stability matters.

template<typename RandomIt>
void stable_sort(RandomIt first, RandomIt last);

Stable sort using provided buffer.

template<typename RandomIt>
void stable_sort(RandomIt first, RandomIt last,
                 typename std::iterator_traits<RandomIt>::value_type* buffer);

• Fixed: Integer overflow in range detection for 64-bit types (int64_t, uint64_t) that could cause crashes with random data spanning large ranges
• Perf: Lazy allocation - no longer allocates temp buffer for sorted, reversed, or dense data paths (eliminates ~400KB allocation overhead for these cases)

Contributions are welcome! See CONTRIBUTING.md for guidelines.

MIT License - see LICENSE for details.

If you use tieredsort in academic work:

@software{tieredsort2025,
  title = {tieredsort: A 3-Tier Adaptive Sorting Algorithm for Numeric Types},
  author = {Cranot},
  year = {2025},
  url = {https://github.com/Cranot/tieredsort}
}

Built on research and inspiration from:

tieredsort - Fast sorting without SIMD
Made by Dimitris Mitsos & AgentsKB.com
Using Deep Research