BIT DIVISION SORT

An In-Place, MSB Radix Sort Algorithm

🚀 O(N × Bits) 💾 In-Place 🔢 Integer Only

What is Bit Division Sort?

The provided algorithm is a variation of Quick Sort that uses bits instead of a pivot element to partition the array. It is formally known as Binary Quick Sort or In-Place MSB Radix Sort.

Core Concept

Instead of comparing numbers to each other (like if a > b), it checks specific bits in the binary representation. It starts at the Most Significant Bit (MSB) and groups numbers into two buckets:

  • 0 Numbers with the bit 0 (Left Side)
  • 1 Numbers with the bit 1 (Right Side)

The Java Implementation

if ((arr[inStart] & (1 << bits)) != 0) {
    swap(arr, inStart, inEnd);
    inEnd--;
} else {
    inStart++;
}

This core loop moves "1-bit" numbers to the end and keeps "0-bit" numbers at the start.

Visual Execution Trace

Tracing the algorithm on the provided array at Bit 6 (Value 64).

1. Input Array

42
17
89
5
33
71
24
60
9
56

2. The Filter Mechanism (Bit 6)

64
0100 0000
Mask (1 << 6)
➜

The Rule:

Is number & 64 non-zero?

  • No (0) → Stay Left
  • Yes (64) → Swap to Right

3. Partition Result (Level 1)

Bit 6 is 0 (< 64)
42 17 5 33 24 60 9 56
Bit 6 is 1 (≥ 64)
89 71

The algorithm then recursively calls itself on the Green and Red buckets using Bit 5 (32).

Performance

Comparison between standard Merge/Quick Sort and Bit Division Sort for integers.

Best Case O(N × B)
Worst Case O(N × B)
* Where N is array length and B is number of bits (e.g., 32).

Space Complexity

O(B)

The space complexity is determined by the recursion stack depth, which is equal to the number of bits (B). It does not require auxiliary arrays.

Advantages & Limitations

👍 Advantages

  • 1

    Linear-ish Time: Does not depend on comparisons. Can be faster than O(N log N) when N is very large and bits (B) is small.

  • 2

    In-Place: Uses the existing array for partitioning, saving memory compared to standard Radix Sort.

  • 3

    Cache Friendly: Access patterns are sequential during the partition scan.

👎 Limitations

  • 1

    Data Type Restricted: Only works effectively on integers or data with direct binary representation.

  • 2

    Unstable: The swapping mechanism (seen in the code) changes the relative order of equal elements.

  • 3

    Recursion Overhead: Deep recursion for 32-bit or 64-bit integers can add function call overhead.

Conclusion

The Bit Division Sort is a powerful algorithm for specific use cases involving integer sorting. While less generic than QuickSort, it leverages the fundamental binary nature of computers to organize data efficiently.