Metadata-Version: 2.4
Name: qi_sort
Version: 0.4.0
Summary: qi-sort & qi::apex: High-Performance Adaptive Sorting Suite for Modern Hardware
Home-page: https://github.com/PandiaJason/qi-sort
Author: Jason Pandia
License: GPL-2.0-only
Project-URL: Homepage, https://github.com/PandiaJason/qi-sort
Project-URL: Repository, https://github.com/PandiaJason/qi-sort.git
Keywords: sorting,radix-sort,c++17,high-performance,adaptive-sort,apex,simd
Classifier: Development Status :: 5 - Production/Stable
Classifier: Intended Audience :: Developers
Classifier: Topic :: Software Development :: Libraries
Classifier: Programming Language :: C++
Classifier: Programming Language :: Python :: 3
Requires-Python: >=3.8
Description-Content-Type: text/markdown
License-File: LICENSE
Dynamic: home-page
Dynamic: license-file
Dynamic: requires-python

<div align="center">

<img src="https://img.shields.io/badge/qi--sort-blueviolet?style=for-the-badge&labelColor=0d1117" alt="qi-sort" height="48"/>

# `qi-sort` & `qi::apex`
### Ultra-High-Performance Adaptive Sorting Suite for Modern Hardware

<p align="center">
  A <b>zero-dependency, single-header</b> C++17 adaptive sorting engine with <b>Go, Python, and Java</b> bindings.<br/>
  Featuring <b><code>qi::apex</code></b> (Strict 20 KB L1-Bound, 8-Way ILP Radix-11, Universal Multi-Type Engine)<br/>
  delivering <b>6.4× speedup over <code>std::sort</code></b> and up to <b>3,095 MKeys/s</b> on real-world datasets.
</p>

<p align="center">
  <a href="LICENSE"><img src="https://img.shields.io/badge/License-GPL_v2-blue.svg?style=flat-square" alt="License: GPL v2"/></a>
  <a href="include/qi_apex.hpp"><img src="https://img.shields.io/badge/C%2B%2B-17-00599C?style=flat-square&logo=c%2B%2B" alt="C++17"/></a>
  <a href="#benchmark-scorecards"><img src="https://img.shields.io/badge/Tested--On-Apple_Silicon_%7C_Intel_Xeon-blueviolet?style=flat-square" alt="Tested Platforms"/></a>
  <a href="https://pypi.org/project/qi-sort/"><img src="https://img.shields.io/badge/pip_install-qi--sort-3776AB?style=flat-square&logo=python&logoColor=white" alt="PyPI Package"/></a>
  <a href="bindings/go"><img src="https://img.shields.io/badge/Go-Module-00ADD8?style=flat-square&logo=go&logoColor=white" alt="Go Module"/></a>
  <a href="bindings/java"><img src="https://img.shields.io/badge/Java-JNI-ED8B00?style=flat-square&logo=openjdk&logoColor=white" alt="Java JNI"/></a>
  <a href="include/qi_apex.hpp"><img src="https://img.shields.io/badge/header--only-yes-brightgreen?style=flat-square" alt="Header Only"/></a>
  <a href="include/qi_apex.hpp"><img src="https://img.shields.io/badge/dependencies-zero-success?style=flat-square" alt="Zero Dependencies"/></a>
</p>

</div>

---

## ⚡ Quickstart (`qi::apex` in C++)

Header-only, zero dependencies. Simply `#include "qi_apex.hpp"`:

```cpp
#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

```text
========================================================================================
  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
```

1. **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.
2. **8-Way ILP Unrolling:** Counting and scatter loops are unrolled 8-way to maximize Instruction-Level Parallelism on superscalar ALU execution ports.
3. **Pipelined Lookahead Software Prefetch ($PF=48$):** Saturates CPU store buffers and hides DRAM cacheline write-allocate latency.
4. **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.
5. **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`](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`](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`](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/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/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/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/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/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/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`)

```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`)

```python
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`)

```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](LICENSE).

```bibtex
@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}
}
```

<div align="center">
<br/>
<sub>Maintained by Jason Pandia · Built with modern C++17, Go, Python & Java · Tested on Apple Silicon & Intel Xeon · GPL-2.0</sub>
</div>
