bsort: A theoretically efficient non-comparison-based sorting algorithm for integer and floating-point numbers
Benjamín Guzmán 1 · 2026
Read bsort: A theoretically efficient non-comparison-based sorting algorithm for integer and floating-point numbers by Benjamín Guzmán 1 (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-08929.txt.
Introduction
Benjamín Guzmán presents bsort, a sorting method that avoids comparisons for integers and floats. The method unifies signed and unsigned integers with floats through a binary-quicksort approach, running in time proportional to word size times input size with word-size extra space. It works best for small word sizes, where tests show it rivals tuned hybrid sorts from popular libraries.
Catalog record
| CREATOR | Benjamín Guzmán 1 |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 36530 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.08929
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
bsort: A theoretically efficient non-comparison-based sorting algorithm for integer and floating-point numbers Benjamín Guzmán 1 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. I Introduction Sorting is a fundamental problem in computer science that involves arranging an input sequence (v_{1},v_{2},...,v_{n}) into a monotonically non-decreasing or non-increasing sequence. Algorithms that solve this problem by comparing pairs of elements are known as comparison-based sorts. It is a well-established result that any such algorithm has a worst-case time complexity lower bound of \Omega(n\ log(n)) [ 2 ] . Non-comparison-based algorithms, such as radix sort, offer a compelling alternative to comparison-based methods, with linear-time performance. In-place variants that operate at the bit-level, such as binary quicksort [ 1 ] , provide a memory-efficient solution but are limited to sorting equally-signed integer values. Extensions to handle sequences with both positive and negative integer elements [ 7 ] and separate out-of-place methods have been extended to handle floating-point values [ 9 ] . This paper aims to present a single, unified algorithm that is simultaneously in-place, and capable of sorting signed and unsigned integers, and floating-point values. II Binary quicksort algorithm The binary quicksort algorithm is a divide-and-conquer algorithm which splits the array a=[a_{1},a_{2},...,a_{n}] based on the bits of its elements. The process is applied recursively, starting from the most significant bit (MSB). In a single partitioning step, the array is split into two sub-arrays, a^{\prime} and a^{\prime\prime} , which satisfy the following invariants: (i) a_{i}\wedge m\neq 0\ \forall a_{i}\in a^{\prime} (ii) a_{j}\wedge m=0\ \forall a_{j}\in a^{\prime\prime} Where \wedge is the bitwise AND operator, and m is a single-bit mask used in the current iteration which is defined by m=1\ll(s-i) where \ll is the left-shift bitwise operator, s\in\mathbb{Z^{+}} is the number of bits every element in a has, and i\in\mathbb{Z}:1\leq i\leq s the current iteration, starting at 1. If a_{1} precedes a_{2} or vice versa depends on the desired sort direction (ascending or descending). After partitioning on one bit, the algorithm recursively sorts these sub-arrays using the mask for the next significant bit. This continues until all s bits have been processed, at which point the array is fully sorted. For example, assuming a=[5,7,1,6,3,4,0] , the entire tracing of the binary quicksort algorithm is illustrated in Fig. 1 : 5 1 01 7 1 11 1 0 01 6 1 10 3 0 11 4 1 00 0 0 00 m 1 00 1 0 0 1 3 0 1 1 0 0 0 0 5 1 0 1 7 1 1 1 6 1 1 0 4 1 0 0 k_{1} m 0 1 0 1 00 1 0 00 0 3 01 1 5 10 1 4 01 0 7 11 1 6 11 0 k_{1} k_{2} k_{2}^{\prime} m 00 1 0 000 1 001 3 011 4 010 5 101 6 110 7 111 m 000 Fig. 1 : Tracing of binary quicksort algorithm bsort uses a modified version of the binary quicksort algorithm as its core sub-procedure, which is described in Algorithm 1, and Algorithm 2 shows how this sub-procedure is used recursively to sort equally-signed integers. 1 Function singlePassBSort(a, m, ps, pe, asc) is 2 Input : a - The array of numbers to be sorted; a_{i}\in a\ \forall\ i\in\mathbb{Z}:0\leq i<|a| m - the current mask; \exists k\in\mathbb{N}_{0}:m=2^{k} ps,pe - the indices at which the partition to be sorted starts (inclusive) and ends (exclusive); ps,pe\in\mathbb{Z}:0\leq ps\leq pe<|a| asc - boolean indicating whether the order is ascending Output : An index k\in[ps,pe] such that a_{i}\wedge m=0,a_{j}\wedge m=m\ \forall i\in[ps,k),j\in[k,pe] if and only if asc is true, or a_{i}\wedge m=m,a_{j}\wedge m=0 otherwise 3 k:=ps 4 for i\leftarrow ps to pe do 5 if (asc\land\neg(a_{i}\wedge m))\lor(\neg asc\land(a_{i}\wedge m)) then 6 swap(a_{i},a_{k}) 7 k\leftarrow k+1 end if 8 end for 9 10 return k end 11 Algorithm 1 bsort sub-procedure to partition an array 1 Function binaryQuickSort(a, m, ps, pe, asc) is 2 Input : Same as singlePassBSort Output : The same array a but with the partition starting at ps and ending at pe (exclusive) now sorted in ascending or descending order depending of asc 3 k:=singlePassBSort(a,m,ps,pe,asc) 4 m^{\prime}:=m\gg 1 5 if m^{\prime}=0 then 6 return a end if 7 8 binaryQuickSort(a,m^{\prime},ps,k,asc) 9 binaryQuickSort(a,m^{\prime},k,pe,asc) 10 return a end 11 Algorithm 2 Binary quicksort for equally-signed integers III bsort The bitwise partitioning mechanism of the standard binary quicksort algorithm is predicated on the lexicographical ordering of unsigned integer representations. Consequently, it is not directly applicable to data types such as signed integers or floating-point numbers, which do not adhere to this ordering principle. Proof . Consider an array a containing two signed integers, a=[x,y] , where x<0 and y\geq 0 . Let w be the word size in bits. In the standard two’s complement representation, the MSB of x is 1, while the MSB of y is 0. The algorithm’s initial partitioning pass, as defined by singlePassBSort , operates on the MSB and partitions the array based on the bitwise AND with the mask m=1\ll(w-1) 1. For element x , x\wedge m=m , since its MSB is 1. 2. For element y , y\wedge m=0 , since its MSB is 0. According to the logic in singlePassBSort , for an ascending sort, elements yielding a non-zero result are placed in the second partition (the “greater” partition), while those yielding zero are placed in the first. Therefore, the partitioning step will incorrectly place x after y . This violates the monotonicity invariant required for a sorted sequence, proving the algorithm fails for mixed-sign integers. \blacksquare This same logic extends to floating-point numbers. Under the IEEE-754 standard, the MSB is also a sign bit. A similar bitwise comparison will incorrectly order negative and positive values for the same reason outlined above. Furthermore, the lexicographical order of the remaining bits does not correspond directly to the numerical magnitude of floating-point values, creating additional sorting failures even within partitions of the same sign. III-A bsort for signed integers The preceding analysis demonstrates that the initial call to singlePassBSort for signed numbers inverts the relative order of the negative and non-negative partitions. For example, in an ascending sort, this erroneously places all negative numbers after all non-negative numbers. To rectify this, we simply invert the sort direction for the initial pass of the algorithm. Algorithm 3 formalizes this procedure. Throughout this paper, a\gg b and a\ggg b denote arithmetic and logical right-shift operations, respectively, e.g., given an 8-bit integer x=-128_{10}=1000\_0000_{2} , then x\gg 1=-64_{10}=1100\_0000_{2} and x\ggg 1=64_{10}=0100\_0000_{2} . The function sizeof(x) returns the bit-width of the operand x . 1 Function bsortSigned(a, asc) is 2 Input : a - an array of signed integers asc - boolean indicating the sorting order Output : The same array a but sorted 3 m:=1\ll(sizeof(a_{0})-1) 4 k:=singlePassBSort(a,m,0,|a|,\neg asc) 5 m^{\prime}:=m\ggg 1 6 binaryQuickSort(a,m^{\prime},0,k,asc) 7 binaryQuickSort(a,m^{\prime},k,|a|,asc) 8 return a end 9 Algorithm