Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2509.19021 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917276135981056 |
|---|---|
| author | Pandey, Atharv Kuppusamy, Lakshmanan |
| author_facet | Pandey, Atharv Kuppusamy, Lakshmanan |
| contents | Sorting is a foundational primitive of computer science and optimizations in sorting subroutines can cascade into significant performance gains for high-throughput systems. In this paper, we analyze the inefficiencies of a non-comparison sorting algorithm, namely, Base-n Radix Sort (BNRS), specifically the `zero padding' problem in skewed datasets. We develop an execution model, called, Stable Partitioning - Least Significant Digit Radix Sort (shortly, SP-LSD), an iterative least significant digit based pruning model designed to address this inefficiency. Based on this development, we derive the Radix Crossover Framework(RCF), an analytic three-point decision framework. The framework is established on the precondition of non-negative integers, which enables the derivation of three critical boundaries. First, the Asymptotic Crossover ($k<n^{\log_2 n}$) defines when BNRS and SP-LSD can theoretically outperform the comparison sorting algorithms where k is the maximum value and n is the input size. Second, the Round-feasibility Crossover ($k>n^2$) defines when overhead cost of implemented model SP-LSD is amortized. Third, we derive Pruning Crossover parameterized by the ratio of random-access sorting cost to sequential partitioning cost. This model demonstrates that SP-LSD yields a net gain on skewed and uniform distributions over standard BNRS. The experimental results are consistent with the crossover boundaries, providing a deterministic roadmap for adaptive algorithm selection. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_19021 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Predictive Framework for Base-n Radix Sort Optimization Pandey, Atharv Kuppusamy, Lakshmanan Data Structures and Algorithms Sorting is a foundational primitive of computer science and optimizations in sorting subroutines can cascade into significant performance gains for high-throughput systems. In this paper, we analyze the inefficiencies of a non-comparison sorting algorithm, namely, Base-n Radix Sort (BNRS), specifically the `zero padding' problem in skewed datasets. We develop an execution model, called, Stable Partitioning - Least Significant Digit Radix Sort (shortly, SP-LSD), an iterative least significant digit based pruning model designed to address this inefficiency. Based on this development, we derive the Radix Crossover Framework(RCF), an analytic three-point decision framework. The framework is established on the precondition of non-negative integers, which enables the derivation of three critical boundaries. First, the Asymptotic Crossover ($k<n^{\log_2 n}$) defines when BNRS and SP-LSD can theoretically outperform the comparison sorting algorithms where k is the maximum value and n is the input size. Second, the Round-feasibility Crossover ($k>n^2$) defines when overhead cost of implemented model SP-LSD is amortized. Third, we derive Pruning Crossover parameterized by the ratio of random-access sorting cost to sequential partitioning cost. This model demonstrates that SP-LSD yields a net gain on skewed and uniform distributions over standard BNRS. The experimental results are consistent with the crossover boundaries, providing a deterministic roadmap for adaptive algorithm selection. |
| title | A Predictive Framework for Base-n Radix Sort Optimization |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2509.19021 |