Comparison-based sorting hit its theoretical floor decades ago: O(n log n) comparisons, and you cannot do better. Non-comparison sorts — radix sort, counting sort — bypass the floor by exploiting the representation of the data, achieving O(wn) time for w-bit keys. The space of non-comparison sorting algorithms is considered well-explored.
The paper (arXiv:2603.08929, March 2026) introduces bsort, a non-comparison sorting algorithm based on binary quicksort principles that achieves O(wn) time and O(w) space for integers and floating-point numbers. The algorithm is practically competitive with optimized standard-library implementations despite its simplicity.
The contribution is not a new asymptotic result — O(wn) was already achievable. It is a new point in the design space: simple enough to implement in a few dozen lines, space-efficient (O(w) rather than O(n)), and fast in practice on real hardware. The algorithm works by binary partitioning on successive bits — like quicksort, but the “pivot” at each level is determined by a bit position rather than a data value, eliminating the pathological cases that plague quicksort's worst case.
The structural lesson: a well-explored algorithmic landscape can still contain simple, practical solutions that were missed because researchers optimized for the wrong metric. The radix sort family optimized for time complexity; quicksort optimized for comparison count; bsort occupies a niche — minimal space, no comparisons, practical speed — that falls between the established families. The gap was in the design space, not in the theory.