Tieredsort: Header only, blazing fast (3-4x) C++17 sorting for numeric types

Summary

tieredsort A fast, header-only C++17 sorting library for numeric types Quick Benchmark (n=100,000) 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 on random data 16-21x faster on dense/few-unique data on dense/few-unique data 6.2x faster on Zipf distributions What is tieredsort? 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! Performance Benchmark Methodology 20 timed runs per seed, 3 warmup runs per seed, 5 different random seeds to avoid data bias to avoid data bias Rotating algorithm order to avoid cache bias to avoid cache bias Reporting median with IQR (interquartile range) with IQR (interquartile range) Compiled with GCC 13.1, -O3 -std=c++17 -march=native Synthetic Patterns (n = 100,000) Pattern std::sort tieredsort vs std Random 5,364 us 1,494 us 3.6x Sorted 1,442 us 1,440 us 1.0x Reversed 1,123 us 1,148 us 0.98x Nearly Sorted 2,009 us 2,081 us 0.97x Few Unique (10) 2,595 us 159 us 16.3x Dense (0-100) 3,347 us 159 us 21.1x Organ Pipe 6,820 us 6,715 us 1.0x Zipf 4,278 us 685 us 6.2x Scaling Benchmark (Random Data) Size std::sort tieredsort Speedup 1,000 29 us 11 us 2.5x 10,000 437 us 218 us 2.0x 100,000 5,358 us 1,489 us 3.6x 500,000 30,974 us 9,750 us 3.2x 1,000,000 65,216 us 20,602 us 3.2x Type Performance (n = 100,000) Type std::sort tieredsort Speedup int32_t 5,519 us 1,481 us 3.7x uint32_t 5,218 us 1,475 us 3.5x int64_t 5,416 us 3,211 us 1.7x uint64_t 5,403 us 3,962 us 1.4x float 7,370 us 1,433 us 5.1x double 7,506 us 4,132 us 1.8x Correctness Validation ✓ All tests passed with 100% ...