BINARY TRIE-BASED SORTING SYSTEM
BitSort is a non-comparison based sorting algorithm. It utilizes a binary trie structure to organize elements bit by bit, resulting in a predictable time complexity relative to the bit-depth of the input data type.
O(N * K)
N: Total elements
K: Bit size (e.g., 32 for int)
DYNAMIC
Directly proportional to unique element distribution.
The algorithm decomposes each integer into its constituent bits, traversing from MSB to LSB. Each bit determines the path taken through a binary tree of 'Blocks'.
The core structure uses a memory-efficient union to represent internal nodes and leaves.
typedef union Block {
int cnt[2]; // Leaf: bit counters
Block* node[2]; // Internal: child pointers
} Block;| N (Count) | Distribution | Memory Usage | Duration |
|---|---|---|---|
| 1,000,000 | Same Value | 512 Bytes | ~0.02s |
| 1,000,000 | Sequential | ~16 MB | ~0.2s |
| 1,000,000 | Uniform Random | ~179 MB | ~1.4s |