Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2605.16667 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909049243566080 |
|---|---|
| author | Narvaez, Alexander |
| author_facet | Narvaez, Alexander |
| contents | Sorting over bounded-universe integer keys has traditionally relied on counting sort and radix sort, both of which incur mandatory prefix-sum passes, auxiliary scatter buffers, or multiple permutation passes. This paper introduces DialSort, a non-comparative sorting architecture based on the self-indexing principle: each integer key simultaneously encodes its value and its canonical position in the ordered address space [0,U-1]. DialSort eliminates the prefix-sum pass entirely by treating the histogram H as the canonical ordered representation, not as an intermediate structure.
To support parallel ingestion without serialization, we introduce the Conflict Resolution Network (CRN), a pipelined additive reduction tree that resolves concurrent writes using equality checks exclusively, with no magnitude comparisons. Formal proofs establish O(n+U) sequential and O(n/k + log k + U) parallel time bounds.
A software prototype on an 8-thread Intel x86-64 achieves 39.77x speedup over std::sort and peak throughput of 115.9 M keys/s. Against Classic Counting Sort, DialSort wins 46 of 48 configurations. Against IPS4o, DialSort outperforms it in 24 of 48 sequential and 29 of 48 parallel configurations. Against ska_sort, it wins 46 of 48 configurations. All 208 benchmark configurations passed correctness verification.
DialSort is not a universal replacement for comparison-based sorting, but a domain-specialized architecture for bounded-universe workloads where sorting reduces to a geometric read over memory. Benchmark source and five open interactive simulators are released alongside this paper. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_16667 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | DialSort: Non-Comparative Integer Sorting via the Self-Indexing Principle: Architecture, Implementation, and Substrate-Aware Analysis Narvaez, Alexander Data Structures and Algorithms Sorting over bounded-universe integer keys has traditionally relied on counting sort and radix sort, both of which incur mandatory prefix-sum passes, auxiliary scatter buffers, or multiple permutation passes. This paper introduces DialSort, a non-comparative sorting architecture based on the self-indexing principle: each integer key simultaneously encodes its value and its canonical position in the ordered address space [0,U-1]. DialSort eliminates the prefix-sum pass entirely by treating the histogram H as the canonical ordered representation, not as an intermediate structure. To support parallel ingestion without serialization, we introduce the Conflict Resolution Network (CRN), a pipelined additive reduction tree that resolves concurrent writes using equality checks exclusively, with no magnitude comparisons. Formal proofs establish O(n+U) sequential and O(n/k + log k + U) parallel time bounds. A software prototype on an 8-thread Intel x86-64 achieves 39.77x speedup over std::sort and peak throughput of 115.9 M keys/s. Against Classic Counting Sort, DialSort wins 46 of 48 configurations. Against IPS4o, DialSort outperforms it in 24 of 48 sequential and 29 of 48 parallel configurations. Against ska_sort, it wins 46 of 48 configurations. All 208 benchmark configurations passed correctness verification. DialSort is not a universal replacement for comparison-based sorting, but a domain-specialized architecture for bounded-universe workloads where sorting reduces to a geometric read over memory. Benchmark source and five open interactive simulators are released alongside this paper. |
| title | DialSort: Non-Comparative Integer Sorting via the Self-Indexing Principle: Architecture, Implementation, and Substrate-Aware Analysis |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2605.16667 |