qi-sort & qi::apex
Ultra-High-Performance Adaptive Sorting Suite for Modern Hardware
A zero-dependency, single-header C++17 adaptive sorting engine with Go, Python, and Java bindings.
Featuring qi::apex (Strict 20 KB L1-Bound, 8-Way ILP Radix-11, Universal Multi-Type Engine)
delivering 6.4× speedup over std::sort and up to 3,095 MKeys/s on real-world datasets.
⚡ Quickstart (qi::apex in C++)
Header-only, zero dependencies. Simply #include "qi_apex.hpp":
#include "include/qi_apex.hpp"
#include <vector>
#include <iostream>
int main() {
// 1. Unsigned 32-bit Integer Sort (3.18 ms for 1M keys)
std::vector<uint32_t> u32_data = {42, 10, 100, 5, 9999, 12};
qi::apex::sort(u32_data);
// 2. Signed 32-bit Integer Sort (Negative numbers handled in-place)
std::vector<int32_t> i32_data = {-500, 120, -999, 45, 0};
qi::apex::sort(i32_data);
// 3. IEEE 754 32-bit Float Sort (Sign-magnitude order preservation)
std::vector<float> f32_data = {-3.14f, 0.0f, 99.8f, -0.001f};
qi::apex::sort(f32_data);
// 4. 64-bit Integer Sort (4-Pass Radix-16 Engine)
std::vector<uint64_t> u64_data = {1000000000000ULL, 500ULL, 42ULL};
qi::apex::sort(u64_data);
// 5. Database Column ORDER BY (Key-Payload Tuple Pairs)
std::vector<uint32_t> column_keys = {40, 10, 30};
std::vector<uint64_t> row_ids = {101, 102, 103};
qi::apex::sort_pairs(column_keys.data(), row_ids.data(), column_keys.size());
// 6. Lock-Free Multi-Core Parallel Sort
qi::apex::parallel_sort(u32_data);
}
🏆 Benchmark Scorecards
1. Official Best-of-3 Benchmark (qi::apex vs Radix vs qi::sort vs std::sort)
Hardware: Apple Silicon M1 Pro | Compiler:
clang++ -O3 -std=c++17| Runs: Best of 3
========================================================================================
OFFICIAL BENCHMARK: qi::apex vs Standard Radix vs qi::sort vs std::sort
========================================================================================
--- N = 100,000 Uniform Random 32-bit Keys ---
Algorithm / Engine Time (ms) Throughput (MKeys/s) Status
----------------------------------------------------------------------------------------
std::sort (C++ Introsort) 1.97 50.67 PASS
Standard Radix-8 (4 Passes) 0.89 112.40 PASS
Standard Radix-16 (2 Passes) 0.97 103.46 PASS
qi::sort (v0.3.61 Baseline) 0.62 160.02 PASS
★ qi::apex (Single-Core Champion) 0.58 173.25 PASS
★ qi::apex (Multi-Core PARALLEL) 0.58 172.99 PASS
----------------------------------------------------------------------------------------
--- N = 1,000,000 Uniform Random 32-bit Keys ---
Algorithm / Engine Time (ms) Throughput (MKeys/s) Status
----------------------------------------------------------------------------------------
std::sort (C++ Introsort) 20.82 48.03 PASS
Standard Radix-8 (4 Passes) 4.49 222.84 PASS
Standard Radix-16 (2 Passes) 4.31 232.05 PASS
qi::sort (v0.3.61 Baseline) 3.44 290.95 PASS
★ qi::apex (Single-Core Champion) 3.18 314.66 PASS (RECORD)
★ qi::apex (Multi-Core PARALLEL) 2.27 440.00 PASS
----------------------------------------------------------------------------------------
--- N = 10,000,000 Uniform Random 32-bit Keys ---
Algorithm / Engine Time (ms) Throughput (MKeys/s) Status
----------------------------------------------------------------------------------------
std::sort (C++ Introsort) 227.39 43.98 PASS
Standard Radix-8 (4 Passes) 54.12 184.76 PASS
Standard Radix-16 (2 Passes) 47.84 209.01 PASS
qi::sort (v0.3.61 Baseline) 38.00 263.18 PASS
★ qi::apex (Single-Core Champion) 36.82 271.58 PASS
★ qi::apex (Multi-Core PARALLEL) 15.75 634.75 PASS
----------------------------------------------------------------------------------------
--- N = 10,000,000 Keys (Duplicates: Values 0–255) ---
Algorithm / Engine Time (ms) Throughput (MKeys/s) Status
----------------------------------------------------------------------------------------
Standard Radix-8 (4 Passes) 142.00 70.42 PASS
★ qi::apex (Adaptive Counting Sort) 4.15 2,407.17 PASS
----------------------------------------------------------------------------------------
--- N = 10,000,000 Keys (Already Sorted - O(N) Test) ---
Algorithm / Engine Time (ms) Throughput (MKeys/s) Status
----------------------------------------------------------------------------------------
Standard Radix-8 (4 Passes) 158.14 63.24 PASS
★ qi::apex (1ns Monotonic Short-Circuit) 4.38 2,281.95 PASS
========================================================================================
2. World Championship (qi::apex vs World's Fastest Open-Source Sorters)
| Dataset ($N = 10,000,000$) | std::sort |
Rust pdqsort |
ska_sort (Radix) |
qi::sort (v0.3.61) |
qi::apex (Champion) |
qi::apex Speedup |
|---|---|---|---|---|---|---|
| Uniform Random 32-bit | 229.07 ms | 222.72 ms | 174.29 ms | 36.48 ms | 36.02 ms |
6.2× FASTER |
| Narrow Domain (0–255) | 77.15 ms | 59.12 ms | 74.61 ms | 4.06 ms | 4.01 ms |
14.7× FASTER |
| Medium Domain (0–65535) | 133.28 ms | 108.86 ms | 68.49 ms | 38.87 ms | 20.97 ms |
5.2× FASTER |
| Nearly Sorted (95%) | 120.04 ms | 128.96 ms | 160.99 ms | 110.97 ms | 96.21 ms |
1.3× FASTER |
| Duplicates (1000 Unique) | 89.89 ms | 70.70 ms | 79.97 ms | 4.69 ms | 4.77 ms |
14.8× FASTER |
| Fully Pre-Sorted ($O(N)$) | 10.61 ms | 7.95 ms | 133.90 ms | 4.27 ms | 4.28 ms |
1.9× FASTER |
🏗️ Architectural Foundations of qi::apex
qi::apex achieves its speed through 5 physical hardware optimizations:
Input Data Array
│
▼
┌───────────────────────┐
│ 50ns Bitwise Probe │
│ bitOr + lsbOccupied │
└───────────┬───────────┘
│
┌───────┬───────┼───────┬───────┐
▼ ▼ ▼ ▼ ▼
Tier 0 Tier 1 Tier 2 Tier 3 Tier 4
O(N) Counting Radix-8 Radix-11 Radix-16
Monotonic (≤4095) (≤65535) Strict 20KB (Duplicates)
Fast Linear Compact 8-Way ILP 2 Passes
Path Pass Passes L1-Bound 65K Bins
│ │ │ │ │
└───────┴───────┴───────┴───────┘
▼
Sorted Output Vector
- Strict 20 KB L1 Cache Bounding: Total histogram size ($2048 \times 4\text{B} + 2048 \times 4\text{B} + 1024 \times 4\text{B} = 20\text{ KB}$) is guaranteed to fit 100% inside 32KB/48KB Intel/AMD L1-D cache and 128KB Apple Silicon L1-D cache, preventing L2 thrashing.
- 8-Way ILP Unrolling: Counting and scatter loops are unrolled 8-way to maximize Instruction-Level Parallelism on superscalar ALU execution ports.
- Pipelined Lookahead Software Prefetch ($PF=48$): Saturates CPU store buffers and hides DRAM cacheline write-allocate latency.
- 1ns Monotonic Fast-Rejection: Tests initial elements inline, bailing out in 2–3 clock cycles on random data while executing in $O(N)$ on pre-sorted data.
- Adaptive Kernel Routing: Dispatches instantly to counting sort ($\le 4,095$), compact Radix-8 ($\le 65,535$), 2-pass Radix-16 (heavy duplicates), or 3-pass L1-bound Radix-11 (full 32-bit).
🧬 Complete Catalog of QI Models & Research Engines
| Model | Path | Category | Core Mechanism & Insight |
|---|---|---|---|
qi::apex (Ultimate) |
include/qi_apex.hpp |
Production Flagship | Strict 20 KB L1 footprint, 8-way ILP unrolling, universal types (u32, i32, f32, u64, i64, f64, sort_pairs). 314.7 MKeys/s. |
qi::sort (v0.3.61) |
include/qi_radix.hpp |
Production Baseline | 50ns bitwise state probing, counting sort fast-path, C-ABI, Python, Java, and Go bindings. |
QI-FieldSort |
research/qi_field_sort.hpp |
100% Non-Radix | Continuous potential density field $\Phi(x)$ inversion with 16-element Bitonic sorting networks. Zero bit-shifts. |
QI-WaveSort |
research/qi_wave_sort.hpp |
Research | Continuous wavefunction collapse with 8 KB L1-resident write-combining software block caches. |
QI Partition Sort |
research/qi_partition_sort.hpp |
Research | Fixed-point Q32.32 micro-bucket partitioning without bitwise masks. Runs in 35.8 ms on narrow domains. |
qi_turbo |
research/qi_turbo_radix.hpp |
Research | 4-banked dual-histogram counting to eliminate CPU Read-After-Write (RAW) pipeline hazard stalls. |
QI-LearnedSplineSort |
research/qi_learned_spline_sort.hpp |
Research | 64-knot empirical CDF spline fitted in 50ns to project elements directly into rank positions with Bitonic cleanup. |
QI-InPlaceCyclicSort |
research/qi_inplace_cyclic_sort.hpp |
Research | Zero-allocation in-place cycle-following permutation requiring $O(1)$ auxiliary RAM. |
QI-SIMDVectorSort |
research/qi_simd_vector_sort.hpp |
Research | In-register SIMD Bitonic sorting networks sorting 16 elements simultaneously in CPU vector registers (408 MKeys/s). |
🌐 Language Bindings
1. Go (github.com/PandiaJason/qi-sort/bindings/go)
package main
import (
"github.com/PandiaJason/qi-sort/bindings/go"
)
func main() {
data := []uint32{10543, 42, 999999, 12, 0, 8881}
qisort.Sort(data)
}
2. Python (pip install qi-sort)
import numpy as np
import qi_sort
# Zero-copy in-place sort on NumPy array
arr = np.random.randint(0, 1000000, size=1000000, dtype=np.uint32)
qi_sort.sort_numpy(arr)
3. Java / JNI (bindings/java)
import com.qisort.QiSort;
public class Main {
public static void main(String[] args) {
int[] data = {42, 10, 100, 5, 9999, 12};
QiSort.sort(data);
}
}
📂 Repository Structure
qi-sort/
├── include/
│ ├── qi_apex.hpp # ← C++17 single-header ULTIMATE engine (qi::apex)
│ ├── qi_radix.hpp # ← C++17 single-header baseline engine (qi::sort)
│ ├── qi_beast.hpp # ← Forwarding alias header
│ └── qi_c_api.h # C-ABI interface (Python / Java / Rust / Go)
├── research/
│ ├── qi_field_sort.hpp # 100% Non-Radix Continuous Density-Field Inversion Sort
│ ├── qi_wave_sort.hpp # Wavefunction Collapse with Software Block Cache
│ ├── qi_partition_sort.hpp # Fixed-Point Q32.32 Micro-Bucket Rank Partitioning
│ ├── qi_turbo_radix.hpp # 4-Banked Dual-Histogram Radix-11
│ ├── qi_learned_spline_sort.hpp # 1-Pass Learned 64-Knot Empirical Spline Sorter
│ ├── qi_inplace_cyclic_sort.hpp # Zero-Allocation O(1) Memory In-Place Permutation Sort
│ └── qi_simd_vector_sort.hpp # In-Register SIMD Vector Bitonic Sorting Networks
├── bindings/
│ ├── go/ # Go native module & CGO wrapper
│ ├── python/ # Python ctypes & NumPy integration
│ └── java/ # Java JNI wrapper
├── benchmarks/
│ ├── benchmark_qi_apex.cpp # Official Best of 3 Benchmark (apex vs std vs radix)
│ ├── world_championship_benchmark.cpp # Global World Championship (apex vs pdqsort vs ska_sort)
│ ├── compare_all_qi_models.cpp # Complete QI Family Model Arena
│ └── real_world_database_benchmark.cpp # 40M row columnar database benchmark
├── examples/
│ ├── basic_usage.cpp # C++ basic usage demo
│ ├── database_column_sort.cpp # Columnar sort demo
│ └── spatial_morton_sort.cpp # Geospatial Z-order curve demo
├── CMakeLists.txt
├── LICENSE # GNU General Public License v2.0
└── README.md
📜 License & Citation
Licensed under the GNU General Public License v2.0 — see LICENSE.
@software{pandia2026qisort,
title = {qi-sort & qi::apex: High-Performance Adaptive Sorting Suite},
author = {Pandia, Jason},
year = {2026},
url = {https://github.com/PandiaJason/qi-sort},
license = {GPL-2.0}
}
Maintained by Jason Pandia · Built with modern C++17, Go, Python & Java · Tested on Apple Silicon & Intel Xeon · GPL-2.0
Metadata
Release files for qi-sort 0.4.0
For a detailed explanation of source distributions (sdists) and built distributions (wheels), please see the package formats documentation.
Source distribution (sdist)
| File | Size | Uploaded | Provenance | Actions |
|---|---|---|---|---|
| qi_sort-0.4.0.tar.gz | 50.7 kB | Without provenance | Details for qi_sort-0.4.0.tar.gz |
Release files / qi_sort-0.4.0.tar.gz
| Download URL | qi_sort-0.4.0.tar.gz |
|---|---|
| Size | 50.7 kB |
| Tags | Source |
|
SHA-256 checksum How to use checksums |
c005b34075729d2964acf72a0214775f051a4790c30122ade6100c641bc839c8
|
|
BLAKE2b-256 checksum How to use checksums |
0cfbc9a20ebe2a682445bd4168db8b7d36e3a61e2e274db2ec530ac3aaa95e58
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/7.0.0 CPython/3.12.11
|
Security for qi-sort 0.4.0
Provenance
Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.
No provenance found
None of the files in this release were uploaded with provenance metadata.
A note on package security
PyPI is a repository for distributing packages, not a service for auditing them. While third-party security researchers and our staff do their best to detect and remove malicious packages, PyPI cannot guarantee the quality, security or suitability of any given package.
To learn more about protecting yourself from malicious actors, visit our package security documentation.