bsort: A theoretically efficient non-comparison-based sorting algorithm for integer and floating-point numbers
Abstract
This paper presents bsort, a non-comparison-based sorting algorithm for signed and unsigned integers, and floating-point values. The algorithm unifies these cases through an approach derived from binary quicksort, achieving $O(wn)$ runtime asymptotic behavior and $O(w)$ auxiliary space, where $w$ is the element word size. This algorithm is highly efficient for data types with small word sizes, where empirical analysis exhibits performance competitive with highly optimized hybrid algorithms from popular libraries.
Fields of Study & Subjects
Algorithms and Data Compression
Parallel Computing and Optimization Techniques
Logic
programming
and type systems
Publication details
- Journal / source
- arXiv (Cornell University)
- Publication date
- 9 March 2026
- Language
- EN
- Document type
- Preprint