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.
Note (2026-11-12): checked against the paper's full text. The O(wn) time and O(w) auxiliary space match the paper, and so does the summary that it is derived from binary quicksort. The paper's claim is narrower than the essay's on speed: it is highly efficient for data types with small word sizes, where it is competitive with highly optimized hybrid library algorithms, and its own analysis shows high L1 cache miss rates and the cost of recursion down to the last bit. The paper's stated aim is a single in-place algorithm that handles signed and unsigned integers and floating-point values (plain binary quicksort handles only equally signed integers); the essay's claim that the bit-position pivot removes quicksort's pathological cases, and the 'few dozen lines' gloss, are not in the paper.
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.