Search papers, labs, and topics across Lattice.
The paper introduces bsort, a non-comparison-based sorting algorithm applicable to integers and floating-point numbers. Bsort adapts binary quicksort principles to achieve $O(wn)$ time complexity and $O(w)$ space complexity, where $w$ is the word size. Empirical results show bsort's performance is competitive with optimized hybrid sorting algorithms, particularly for data types with small word sizes.
Forget comparison sorts: bsort offers a theoretically efficient $O(wn)$ alternative for sorting integers and floats, rivaling optimized hybrid algorithms in practice.
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.
