CRT Sort

D25: Proprietary sort. CC0.

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

How It Works

CRT Radix Sort (PROVED)
Any value in Z/214,414,200 decomposes via CRT into 7 residues with ranges 8, 9, 25, 49, 11, 13, 17. An LSD radix sort through these 7 channels produces a total order in 7 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.
7 passes
One per CRT channel
mod 8, mod 9, mod 25, mod 49, mod 11, mod 13, mod 17. 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 (mod 8, mod 9, mod 25, mod 49, mod 11, mod 13, mod 17). The ring's algebraic structure.

Try It

Array size (2-200):

Generates random values in Z/214,414,200, sorts via 7 CRT counting sort passes. Shows CRT decomposition before and after.

Scaling

CRT radix sort always uses exactly 7 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(7N). 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 7 passes. No adversarial input.ParallelismRecursive divide -- serial dependencies7 independent channels. Sort in parallel.Patent statusProprietary sort optimizations in databasesCC0. Public domain. Forever.

Source code · Public domain (CC0)

Report issue

.ax source compiled to WASM via self-hosting compiler. Zero HTML authored.