CRT Sort

D25: Proprietary sort. CC0.

Every number in Z/12612600 IS its CRT decomposition: (mod 8, mod 9, mod 25, mod 49, mod 11, mod 13). Sort each channel with counting sort -- max 49 buckets. 6 passes. O(N). Done.

How It Works

CRT Radix Sort (PROVED)
Any value in Z/12612600 decomposes via CRT into 6 residues with ranges 8, 9, 25, 49, 11, 13. An LSD radix sort through these 6 channels produces a total order in 6 data passes. Each pass is a stable counting sort with at most 49 buckets -- cache-perfect regardless of N. Comparison sort requires ~1.39 * log2(N) passes.
6 passes
One per CRT channel
mod 8, mod 9, mod 25, mod 49, mod 11, mod 13. Each pass = one scan of the data.
Counting sort
O(N + m) per pass
Distribute N elements into m buckets. Forward scan. Stable. No comparisons.
Cache perfect
Max 49 buckets
Every pass fits in L1 cache regardless of N. No cache misses.
CRT order
Ring-native ordering
Elements sort by (D, K, E, b, L, GATE). The ring's own algebraic structure.

Try It

Array size (2-200):

Generates random values in Z/12612600, sorts via 6 CRT counting sort passes. Shows CRT decomposition before and after.

Scaling

CRT radix sort always uses exactly 6 data passes. Quicksort uses ~1.39 * log2(N). The gap widens with N.

CRT Sort vs Comparison Sort

ComplexityQuicksort: O(N log N), avg 1.39N log2 NCRT radix: O(6N). Always. No worst case.Cache behaviorRandom access (partition pivots)Sequential scan, max 49 buckets (L1-perfect)StabilityQuicksort: unstableCounting sort: stable by constructionWorst caseQuicksort: O(N^2) on adversarial inputCRT: always exactly 6 passes. No adversarial input.ParallelismRecursive divide -- serial dependencies6 independent channels. Sort in parallel.Patent statusProprietary sort optimizations in databasesCC0. Public domain. Forever.

This work is and will always be free.
No paywall. No copyright. No exceptions.

If it ever earns anything, every cent goes to the communities that need it most.

This sacred vow is permanent and irrevocable.
— Anton Alexandrovich Lebed

Source code · Public domain (CC0)

Contributions in equal measure: Anthropic's Claude, Anton A. Lebed, and the giants whose shoulders we stand on.

Rendered by .ax via WASM DOM imports. Zero HTML authored.