DialSort: Non-Comparative Integer Sorting via the Self-Indexing Principle

Read full text Summarise with VIRAT
Authors: Alexander Narváez Berrío
Cited by: 0

Summary

No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.

Summarise with VIRAT Free to try with your Science Catalogs account.

Abstract

Sorting has long been defined by the comparison model and its Ω(n log n) lower bound. We challenge this foundation for bounded-universe integer keys. DialSort is a non-comparative sorting microarchitecture that exploits the self-indexing duality of integers: each key k is simultaneously its value and its natural position in the ordered address space [0, U−1]. Instead of comparing keys, DialSort maps each key directly to its index and resolves concurrent write conflicts through a novel Conflict Resolution Network (CRN) — a pipelined additive reduction tree that uses only equality checks. The sorted output is not computed; it is revealed by a geometric scan of the address space. No order comparison (, or ≤) is ever performed. A software prototype on an 8-thread Intel x86-64 CPU achieves a peak throughput of 115.9 M keys/s and up to 39.77× speedup over std::sort (N=10⁷, U=1024, uniform). Under skewed distributions, DialSort-Parallel reaches 37.97×. For the full int32 range, DialSort-Radix achieves 14.61× speedup at N=10⁷. All 208 benchmark configurations (192 bounded-universe + 16 full-int32) passed correctness verification. Results are fully reproducible from the open-source benchmark v3.1 available at https://github.com/elmaestrotic/dsort. Tier-2 (FPGA) and Tier-3 (photonic) implementations are presented as analytical projections. DialSort demonstrates that, for bounded-universe integer keys, sorting can be interpreted as a geometric reading process, not a comparison problem.

Fields of Study & Subjects

Parallel Computing and Optimization Techniques Algorithms and Data Compression Advanced Database Systems and Queries

Publication details

Journal / source
Zenodo (CERN European Organization for Nuclear Research)
Publication date
22 March 2026
Language
EN
Document type
Preprint