bsort

bsort is a non-comparison-based, linear-time, in-place (with respect to n) sorting algorithm capable of sorting signed/unsigned integers and floating-point values.

Paper at https://doi.org/10.48550/arXiv.2603.08929

Features

• In-place: Does not require extra memory proportional to the input size.
• Non-comparison based: Uses bitwise operations to partition data.
• Linear Time: $O(n \cdot w)$ where $n$ is the number of elements and $w$ is the word-size.
• Constant Space: Formally $O(w)$.
• Type Support:
  • Unsigned Integers (unsigned char, unsigned short, unsigned int, unsigned long long)
  • Signed Integers (char, short, int, long long)
  • Floating Point (float, double)

Usage

bsort is a header-only library. Simply include bsort.h in your project.

#include "bsort.h"
#include <vector>
#include <iostream>

int main() {
    std::vector<double> data = {1.75, 1.25, -2.5, -std::numeric_limits<double>::infinity()};
    
    // Sort ascending (default)
    bsort(data.data(), data.size());
    
    // or, sort descending
    // bsort(data.data(), data.size(), false);

    for (const auto& x : data)
        std::cout << x << " ";
    
    // Output: -inf -2.5 1.25 1.75
    return 0;
}

Build & Test

The project uses CMake for building tests and benchmarks.

Prerequisites

• CMake 3.16+
• C++17 compliant compiler
• Boost (required for spreadsort comparison in tests)

Building

mkdir build && cd build
cmake ..
make

Tests

To validate the algorithm works, the output is compared against introsort and other algos. See bsort_test.cpp. Run:

./build/bsort-test

(./build/bsort-test -h for help)

Benchmarks

To benchmark the algo against other algos Google Benchmark was used. See bsort_benchmark.cpp. Run:

./build/bsort-benchmark --benchmark_format=json > paper/viz/benchmark.json

Performance evaluation with perf

Run

./perf-test.sh

(./perf-test.sh for help)

Future enhancements

The current implementation is monolithic to demonstrate the pure theoretical behavior of the algorithm. Future work could explore:

• Hybridization: Switching to a non-recursive, cache-friendly insertion sort for small partitions to prevent stack pollution.
• SIMD integration: To vectorize bit-masking operations.
• Branchless partitioning: To tackle branch prediction penalties.
• ILP integration: To overlap partitioning tasks.

License

Distributed under the MIT License. See LICENSE for more information.

Author

Benjamín Guzmán

bguzman.dev