Bit Manipulation Sort

Why Sort with Bits?

For years I used quicksort and mergesort without question. They are O(n log n), well-studied, and available in every standard library. Then I needed to sort 100 million 32-bit integers for a data processing pipeline. Quicksort was taking over 30 seconds and consuming gigabytes of memory with its recursive call stack. I switched to a binary radix sort using bit-level partitioning, and the same 100 million integers sorted in under 4 seconds. That was the moment I started paying serious attention to bit manipulation in sorting algorithms.

Bit manipulation sorts exploit the binary representation of data to achieve performance that comparison-based sorts cannot match. They work by examining the individual bits of each element rather than comparing whole values. This approach has two major advantages: it bypasses the O(n log n) lower bound of comparison sorts, and it maps naturally to the CPU's native word-level operations.

I implemented a bit-manipulation sort for a specialized case where I knew all values were in the range 0-65535. By counting bits rather than comparing values, the sort ran in O(n + range) time and was faster than quicksort for my specific data size of 10 million small integers.

Binary Radix Sort (LSD)

Binary radix sort processes integers bit by bit, starting from the least significant bit (LSD). In each pass, it partitions the array based on one bit — elements with a 0 in that position go to the front, elements with a 1 go to the back. After processing all 32 bits (for 32-bit integers), the array is fully sorted.

The key observation is that bit extraction uses a simple shift and AND: (value >> bit) & 1. This is a single CPU instruction — no comparison, no branching, no function call overhead.

// Binary LSD Radix Sort — single bit per pass
function radixSortLSD(arr) {
    const n = arr.length;
    const buffer = new Array(n);

    // Sort by each bit, from LSB to MSB (32 passes for 32-bit ints)
    for (let bit = 0; bit < 32; bit++) {
        // Count how many elements have this bit = 0
        let zeros = 0;
        for (let i = 0; i < n; i++) {
            if (((arr[i] >> bit) & 1) === 0) zeros++;
        }

        // Partition: zeros at the front, ones at the back
        let zeroIdx = 0;
        let oneIdx = zeros;
        for (let i = 0; i < n; i++) {
            if (((arr[i] >> bit) & 1) === 0) {
                buffer[zeroIdx++] = arr[i];
            } else {
                buffer[oneIdx++] = arr[i];
            }
        }

        // Copy back
        for (let i = 0; i < n; i++) arr[i] = buffer[i];
    }
    return arr;
}

// Time: O(32n) = O(n) for fixed-width integers
// Space: O(n) for the buffer array

Optimized Radix Sort (Multi-bit Pass)

Using one bit per pass means 32 passes. Most practical implementations process 8 or 11 bits per pass (using a 256 or 2048 bin counting sort). This reduces passes to 4 (for 32-bit / 8-bit per pass) while still using bitwise operations for bin selection.

// Optimized Radix Sort — 8 bits per pass (4 passes for 32-bit ints)
function radixSort8Bit(arr) {
    const n = arr.length;
    const buffer = new Array(n);
    const counts = new Array(256).fill(0);

    for (let byte = 0; byte < 4; byte++) {
        const shift = byte << 3;  // byte * 8 — bitwise multiplication

        // Count elements in each of the 256 bins
        counts.fill(0);
        for (let i = 0; i < n; i++) {
            const bin = (arr[i] >> shift) & 0xFF; // extract 8 bits
            counts[bin]++;
        }

        // Prefix sum — compute positions
        for (let i = 1; i < 256; i++) counts[i] += counts[i - 1];

        // Place elements in their sorted positions (stable)
        for (let i = n - 1; i >= 0; i--) {
            const bin = (arr[i] >> shift) & 0xFF;
            buffer[--counts[bin]] = arr[i];
        }

        // Swap buffers
        for (let i = 0; i < n; i++) arr[i] = buffer[i];
    }
    return arr;
}

// Only 4 passes instead of 32 — much better cache behavior
// Time: O(4n) = O(n), Space: O(n) + O(256) = O(n)

Bitonic Sort

Bitonic sort is a parallel sorting network that uses a fixed pattern of compare-and-swap operations determined entirely by bit manipulation of indices. Unlike quicksort or mergesort, the comparison sequence is data-independent, which makes it ideal for GPU and FPGA implementations.

The key insight is building a bitonic sequence — one that monotonically increases then decreases. By recursively merging bitonic sequences, the entire array can be sorted in O(log^2 n) parallel steps.

// Bitonic Sort — compare-exchange using bitwise index manipulation
function bitonicSort(arr, ascending = true) {
    const n = arr.length;
    if (n <= 1) return arr;

    // Outer loop: double the bitonic sequence size each iteration
    for (let k = 2; k <= n; k <<= 1) {
        // Inner loop: apply compare-exchange within each bitonic sequence
        for (let j = k >> 1; j > 0; j >>= 1) {
            for (let i = 0; i < n; i++) {
                // Bitwise XOR determines whether this pair should be compared
                const ixj = i ^ j;
                if (ixj > i) {  // only compare each pair once
                    const shouldSwap = ((i & k) === 0) !==
                        ((arr[i] < arr[ixj]) === ascending);
                    if (shouldSwap) {
                        [arr[i], arr[ixj]] = [arr[ixj], arr[i]];
                    }
                }
            }
        }
    }
    return arr;
}

// The compare pattern is deterministic:
// k=2: compare pairs (0,1), (2,3), (4,5), (6,7)
// k=4: compare (0,2), (1,3), (4,6), (5,7), then (0,1), (2,3), (4,5), (6,7)
// k=8: ...and so on until k=n

The inner loop uses the XOR of indices — i ^ j — to determine which element to compare against. This produces a perfect shuffle network that maps directly to GPU warp-level operations. On an NVIDIA GPU with 1024 threads per block, bitonic sort of 1024 elements takes about log^2(1024) = 100 parallel steps, compared to 1024 * log(1024) ≈ 10,000 steps for a sequential quicksort.

Comparison: Bit Sorts vs Traditional Sorts

Each bit-level sort has its sweet spot:

• Radix sort — best for large arrays (millions+) of fixed-width integers. The O(n) time complexity and cache-friendly sequential access pattern make it substantially faster than O(n log n) sorts at scale.
• Bitonic sort — best for GPU/parallel hardware where its deterministic, data-independent comparison pattern maps to SIMD instructions. Used in GPU-based database query engines.
• Bitmap sort — best when the integer range is known and not too large relative to the number of elements. O(n) time, but uses O(range) memory.
• Standard sorts (quicksort, mergesort) — best for non-integer keys, variable-length data, or small arrays where the overhead of bit manipulation is not worthwhile.