Skip to main content
qi-sort

Quantum-Inspired Adaptive Radix Sorting Engine

A zero-dependency, single-header C++17 sorting engine with Go, Python, and Java bindings
featuring 2-Pass Radix-16 zero-memcpy execution, Inverse Participation Ratio (IPR) entropy sensing,
and $O(N)$ branchless short-circuits — delivering 2.2×–6.4× speedups over std::sort on numeric keys.

License: GPL v2 C++17 PyPI Package Go Module Java JNI Header Only Zero Dependencies


Quick Reference

Maintained by:
Jason Pandia (@PandiaJason) and the Open Source Community.

Where to get help:
GitHub Issues or Discussions.

Supported Languages & Bindings:


WHAT IS QI-SORT?

Sorting integer, float, timestamp, and string data is the single most expensive operation inside databases, analytical query engines, dataframes, LSM-tree storage systems, and AI inference engines.

Most sorting libraries give you one static comparison algorithm and hope it fits your data. qi::sort does something different — it uses a high-throughput 2-Pass Radix-16 Zero-Memcpy Engine backed by Inverse Participation Ratio (IPR) distribution sensing and $O(N)$ short-circuits for pre-sorted and reverse-sorted data runs.

It derives its entropy metrics from condensed-matter physics: the Inverse Participation Ratio (IPR) metric ($N_{\text{eff}} = 1 / \sum p_i^2$) used to measure probability concentration across basis states, combined with Shannon entropy analysis across key bytes.


HARDWARE ARCHITECTURE & PLATFORM SCOPING

Sorting performance is strictly governed by physical CPU microarchitecture and memory system topology:

  1. High-Bandwidth Unified Memory Systems (Apple Silicon M-Series / Bare-Metal Multi-Channel DDR5):

    • Unified Memory Bandwidth (~200–800 GB/s) and large SLC/L2 caches favor zero-memcpy out-of-place Radix-16 sorting.
    • On Apple M-Series hardware, qi::sort achieves sub-10ms performance, delivering strong speedups over scalar and NEON comparison sorters (std::sort, pdqsort).
  2. Cloud Virtualized Hypervisors & Wide SIMD Vector Systems (x86-64 Xeon / EPYC / AVX-512):

    • Shared cloud vCPUs have capped memory bandwidth per core (~15–30 GB/s).
    • In-Register SIMD Sorting (hwy::VQSort from Google Highway) processes keys directly in 512-bit ZMM registers (16 MB total DRAM traffic for 2M 32-bit keys). On AVX-512 server nodes, hwy::VQSort is faster than out-of-place radix sorts which move 32 MB of DRAM traffic.
    • On Linux Xeon nodes, qi::sort delivers a consistent 2.2×–6.4× speedup over scalar std::sort for numeric keys, while SIMD vector sorters (vqsort) dominate wide-register vector workloads.

THE "FIXED RADIX TRAP" & RADIX-16 ENGINE

For decades, performance engineers faced a brutal tradeoff between comparison sorting and radix sorting:

  1. Comparison Sorters (std::sort, pdqsort, Google vqsort): Bound by $O(N \log N)$ comparison lower bounds. Comparing keys in scalar or vector registers wastes CPU cycles when sorting uniform integer keys.
  2. Fixed Radix Sorters (Radix-8, Radix-11, Radix-16): Non-comparison $O(k \cdot N)$ speed, but trapped by pass counts:
    • Radix-16: 65,536 histogram buckets (512 KB), completing 32-bit sorting in just 2 passes.
    • Radix-11: 2,048 histogram buckets (16 KB), fitting L1 cache but requiring 3 full passes.

$$\psi_i = \sqrt{p_i}, \qquad \text{IPR} = \sum p_i^2, \qquad N_{\text{eff}} = \frac{1}{\text{IPR}}$$

Applied to byte histograms, $N_{\text{eff}}$ predicts CPU cache pressure.

Kernel Bucket width Count array size Memory passes Best for
Radix-16 16 bits 65,536 (512 KB) 2 Low-entropy, bounded range, pre-sorted, timestamps
Radix-11 11 bits 2,048 (16 KB) 3 High-entropy data where R-16 would trash L2 cache

O(N) Short-Circuits: If sensing detects the data is fully sorted or reverse-sorted (std::reverse), qi::sort completes in $O(N)$ time — achieving up to 27× speedup over standard comparison sorting.


ON WHAT HARDWARE AND SYSTEMS DOES IT RUN?

qi-sort is portable across general-purpose 32-bit and 64-bit architectures:

  • x86-64 / AMD64 (Intel Core, Xeon, AMD Ryzen, EPYC)
  • ARM64 / AArch64 (Apple Silicon M1/M2/M3/M4, AWS Graviton, Ampere Altra)
  • Embedded / Edge (NVIDIA Jetson, Raspberry Pi Compute Module)

Software & Compiler Requirements:

  • C++: Any C++17 compliant compiler (GCC 7+, Clang 5+, MSVC 2019+).
  • Go: Go 1.18+ (Supports Go Generics & static CGO).
  • Python: Python 3.8+ (pip install qi-sort).
  • Java: Java 8+ with JNI native bridge support.

DOCUMENTATION & QUICKSTART

1. C++ (Single-Header, Zero Dependencies)

Include include/qi_radix.hpp in your project:

#include "include/qi_radix.hpp"
#include <vector>
#include <iostream>

struct User {
    uint32_t id;
    std::string name;
};

int main() {
    // A. Standard Vector Sorting
    std::vector<uint32_t> data = {42, 10, 100, 5, 9999, 12};
    qi::sort(data);

    // B. Struct Sorting via Lambda Key Extractor
    std::vector<User> users = {{102, "Alice"}, {100, "Bob"}};
    qi::sort_by(users, [](const User& u) { return u.id; });

    // C. Multi-Threaded Parallel Sort
    qi::sort_parallel(data);

    // D. Asynchronous Background Sort
    qi::sort_async(data, []() { std::cout << "Async sort complete!\n"; });
}

2. Go (Golang Module — 13.14× Faster than slices.Sort)

package main

import (
	"fmt"
	"github.com/PandiaJason/qi-sort/bindings/go"
)

type Employee struct {
	ID   uint32
	Name string
}

func main() {
	// 1. Standard Slice Sort (13.14x faster than slices.Sort)
	data := []uint32{10543, 42, 999999, 12, 0, 8881}
	qisort.Sort(data)

	// 2. Struct Sorting via Go Generics (qisort.SortBy)
	employees := []Employee{{ID: 105, Name: "Charlie"}, {ID: 100, Name: "Bob"}}
	qisort.SortBy(employees, func(e *Employee) uint32 { return e.ID })

	// 3. Multi-Threaded Parallel Sort
	qisort.SortParallel(data)
}

3. Python (pip install qi-sort)

import numpy as np
import qi_sort

# Sort NumPy 1D Array (in-place zero-copy)
arr = np.random.randint(0, 1000000, size=1000000, dtype=np.uint32)
qi_sort.sort_numpy(arr)

# Sort standard Python List
data = [10543, 42, 999999, 12, 0, 8881]
qi_sort.sort(data)

# Non-destructive distribution inspection
stats = qi_sort.analyze(data)
print(stats)

4. Industrial IoT & Supply Chain Interface

#include "examples/iiot_supplychain_interface.hpp"

// High-frequency telemetry time-series buffer sorting
qi::iiot::TelemetryIngestBuffer telemetry;
telemetry.AddReading(1700000005000000ULL, 101, 74.5f);
telemetry.SortByTimestamp();

// Geospatial delivery route spatial clustering (Morton Z-Order)
qi::iiot::LogisticsRouteClusterEngine logistics;
logistics.AddPackage(9001, 37.7749f, -122.4194f);
logistics.ClusterDeliveryRoutes();

5. LLM Inference, RAG & Agentic AI Interface

#include "examples/llm_stream_agentic_interface.hpp"

// LLM Vocabulary Logit Top-K Token Sampling
std::vector<qi::ai::TokenLogit> logits = {{1052, 2.14f}, {812, 12.35f}};
qi::ai::SampleTopKLogits(logits);

// RAG Vector Search Result Reranking
std::vector<qi::ai::VectorSearchResult> rag_docs = {{1001, 0.72f}, {1002, 0.95f}};
qi::ai::RerankVectorResults(rag_docs);

// Agentic AI Context Token Budget Prioritization
std::vector<qi::ai::AgentMemoryNode> memories = {{1, 0.65f, 150, "User context"}};
qi::ai::PrioritizeAgentMemories(memories);

EMPIRICAL VERIFICATION MATRIX ACROSS ALL 21 TEST CASES

Tested on Intel Xeon Platinum 8481C @ 2.70 GHz (g++ 13.3 -O3 -march=native)

Dataset N std::sort std::stable_sort qi::sort Speedup vs std::sort
Uniform Random 1M 33.2 ms 18.7 ms 5.81 ms 5.71× FASTER
Hash Keys 1M 22.3 ms 15.5 ms 4.91 ms 4.53× FASTER
Heavy Duplicates (0–255) 1M 7.87 ms 14.2 ms 3.05 ms 2.57× FASTER
Low Cardinality (16) 1M 5.06 ms 13.8 ms 2.75 ms 1.83× FASTER
Nearly Sorted 95% 1M 10.8 ms 16.3 ms 7.71 ms 1.40× FASTER
Fully Sorted 1M 0.93 ms 7.76 ms 0.34 ms 2.71× FASTER
Reverse Sorted 1M 1.61 ms 11.5 ms 0.56 ms 2.85× FASTER
Uniform Random 3M 64.4 ms 61.6 ms 14.2 ms 4.53× FASTER
Hash Keys 3M 64.0 ms 61.1 ms 13.8 ms 4.62× FASTER
Heavy Duplicates 3M 22.7 ms 58.6 ms 8.73 ms 2.60× FASTER
Low Cardinality 3M 16.8 ms 57.5 ms 8.15 ms 2.06× FASTER
Nearly Sorted 95% 3M 33.5 ms 65.0 ms 31.2 ms 1.07× FASTER
Fully Sorted 3M 2.83 ms 31.6 ms 1.06 ms 2.67× FASTER
Reverse Sorted 3M 4.88 ms 40.4 ms 1.77 ms 2.74× FASTER
Uniform Random 5M 109.7 ms 130.3 ms 27.7 ms 3.95× FASTER
Hash Keys 5M 108.5 ms 127.6 ms 22.3 ms 4.86× FASTER
Heavy Duplicates 5M 39.4 ms 124.4 ms 14.8 ms 2.65× FASTER
Low Cardinality 5M 23.1 ms 121.4 ms 13.4 ms 1.71× FASTER
Nearly Sorted 95% 5M 57.4 ms 134.8 ms 49.4 ms 1.16× FASTER
Fully Sorted 5M 4.68 ms 67.0 ms 1.71 ms 2.72× FASTER
Reverse Sorted 5M 8.15 ms 75.3 ms 2.76 ms 2.95× FASTER

MODULE & BINDING API REFERENCE

C++ Core API (include/qi_radix.hpp)

// Basic Sorting
void qi::sort(std::vector<uint32_t>& data, qi::SortOptions opts = {});
void qi::sort(uint32_t* data, size_t n, qi::SortOptions opts = {});

// Generic Struct Sorting via Lambda Key-Extractor
template <typename Container, typename KeyExtractor>
void qi::sort_by(Container& container, KeyExtractor key_extractor);

// Enterprise Multi-Threaded Parallel & Async Shortcuts
template <typename Container> void qi::sort_parallel(Container& container);
template <typename Container> void qi::sort_async(Container& container, std::function<void()> callback = nullptr);

// Key-Payload (Tuple) ORDER BY Sorting
template <typename Key, typename Payload>
void qi::sort_pairs(Key* keys, Payload* payloads, size_t n);

// String Prefix Radix Sorting
void qi::sort_strings(std::vector<std::string>& strings);

Go API (github.com/PandiaJason/qi-sort/bindings/go)

func qisort.Sort(data []uint32)
func qisort.SortBy[T any](data []T, keyFunc func(element *T) uint32)
func qisort.SortParallel(data []uint32)
func qisort.SortAsync(data []uint32, onComplete func())
func qisort.SortCPP(data []uint32) // CGO Static Wrapper

Python API (qi_sort)

import qi_sort

qi_sort.sort(data_list)
qi_sort.sort_numpy(numpy_array)
stats = qi_sort.analyze(data_list)

REPOSITORY STRUCTURE

qi-sort/
├── include/
│   ├── qi_radix.hpp                      # ← C++17 header-only core
│   ├── qi_sort_univ.hpp                  # Standalone 2-Pass Radix-16 engine
│   └── qi_c_api.h                        # C-ABI interface (Python / Java / Rust / Go)
├── src/
│   ├── qi_c_api.cpp                      # C-ABI implementation
│   ├── qi_jni.cpp                        # Java JNI bridge
│   └── qsort_cli.cpp                     # qsort-db CLI utility
├── bindings/
│   ├── go/                               # Go native module & CGO wrapper
│   │   ├── qisort.go                     # Pure Go 2-Pass Radix-16 & SortBy generics
│   │   ├── iiot.go                       # Industrial IoT & Supply chain Go interface
│   │   ├── iiot_live_stream.go           # Real-time live streaming processor
│   │   ├── ai_stream.go                  # LLM token sampling, RAG & Agentic AI Go interface
│   │   └── cgo_qisort.go                 # CGO static library bridge
│   ├── python/
│   │   ├── qi_sort.py                    # Python ctypes / NumPy integration
│   │   └── test_python.py                # Python benchmark
│   └── java/
│       └── com/qisort/QiSort.java        # Java JNI wrapper
├── benchmarks/
│   ├── online_test.cpp                   # Multi-dataset 7-algorithm benchmark
│   ├── duckdb_orderby_benchmark.cpp      # DuckDB source-level benchmark
│   ├── rocksdb_memtable_benchmark.cpp    # RocksDB MemTable benchmark
│   ├── kernel_selection_ablation.cpp     # Oracle vs QI regret analysis
│   ├── head_to_head.cpp                  # vs pdqsort (Rust std) & ska_sort (Skarupke)
│   ├── parallel_benchmark.cpp            # Multi-threaded parallel scaling benchmark
│   ├── real_data_benchmark.cpp           # NYC taxi + dictionary + airports
│   └── verify_implementation.cpp         # 25-check implementation audit
├── examples/
│   ├── iiot_supplychain_interface.hpp    # IoT & Supply Chain C++ interface
│   ├── iiot_live_stream_server.cpp       # Real-time live streaming IIoT server
│   ├── llm_stream_agentic_interface.hpp  # LLM, RAG & Agentic AI C++ interface
│   ├── llm_stream_agentic_demo.cpp       # LLM, RAG & Agentic AI executable demo
│   └── basic_usage.cpp                   # C++ basic usage
├── 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: Quantum-Inspired Adaptive Radix Sorting Engine},
  author  = {Pandia, Jason},
  year    = {2026},
  url     = {https://github.com/PandiaJason/qi-sort},
  license = {GPL-2.0}
}

Maintained by Jason Pandia · Built with C++17 & Go · Tested on macOS & Linux · GPL-2.0

Metadata

Release files for qi-sort 0.3.38

For a detailed explanation of source distributions (sdists) and built distributions (wheels), please see the package formats documentation.

Source distribution (sdist)

Source distribution for qi-sort 0.3.38
File Size Uploaded Provenance Actions
qi_sort-0.3.38.tar.gz 29.0 kB Without provenance Details for qi_sort-0.3.38.tar.gz

Built distribution (wheel)

Table of built distributions (wheels) for qi-sort 0.3.38
File Interpreter ABI Platform Actions
qi_sort-0.3.38-cp312-cp312-macosx_15_0_arm64.whl CPython 3.12 CPython 3.12 macOS 15.0+ ARM64 Details for qi_sort-0.3.38-cp312-cp312-macosx_15_0_arm64.whl

Total release size: 54.7 kB

Release files / qi_sort-0.3.38.tar.gz

Download URL qi_sort-0.3.38.tar.gz
Size 29.0 kB
Tags Source
SHA-256 checksum
How to use checksums
13d9e6d1ac9b70d1ee7726af9613a56eb32c46a037a5541b62acadf2ad51a21e
BLAKE2b-256 checksum
How to use checksums
c8dc224b83c8df3e43dbf057bf51625fb1253e8ab3ca14cbef4344a4f6c9b95f
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/7.0.0 CPython/3.12.11

Release files / qi_sort-0.3.38-cp312-cp312-macosx_15_0_arm64.whl

Download URL qi_sort-0.3.38-cp312-cp312-macosx_15_0_arm64.whl
Size 25.7 kB
Tags CPython 3.12 macOS 15.0+ ARM64
SHA-256 checksum
How to use checksums
b3835c91dee83f0aad30a438fb326b1f6dab0ccbfaa3fd2548daf6be854b7139
BLAKE2b-256 checksum
How to use checksums
8958d929ce92d85dc95f1d0272acf0b22d165a64f26cf459b119628ee5726282
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.3.38

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.

Release history Release notifications | RSS feed

This release

0.3.38 This release

2 release files No provenance

Anthropic, PBC Visionary sponsor Bloomberg Visionary sponsor Hudson River Trading Visionary sponsor Meta Visionary sponsor NVIDIA Visionary sponsor Microsoft Sustainability sponsor Depot Continuous Integration AWS Cloud computing and Security Sponsor Datadog Monitoring Fastly CDN Google Download Analytics Sentry Error logging StatusPage Status page