Expand description
§Universal Radix Sort
A high-performance, generic Radix Sort implementation for Rust. This library provides a non-comparative sorting algorithm capable of sorting integers, floating-point numbers, and strings with O(n·k) time complexity.
It is designed to outperform standard comparison-based sorts (like QuickSort or MergeSort, which are O(n log n)) when dealing with large datasets of numbers or fixed-length strings.
§Features
- Fast: Linear time complexity O(n·k) where k is the number of bytes/digits
- Universal: Supports
i8-i128,u8-u128,f32,f64, andString - Safe: Handles
NaN,Infinity, empty collections, and edge cases gracefully - Flexible: Supports ascending and descending order
- Memory Efficient: Configurable options for in-place or allocated sorting
- Zero Dependencies: Core functionality has no external dependencies
§Installation
Add this to your Cargo.toml:
[dependencies]
universal_radix_sort = "1.0.0"§Quick Start
§Sorting Integers
use universal_radix_sort::{RadixSort, RadixDataType, SortDirection};
let mut numbers = vec![170, -45, 75, -9000, 802, 24, 2, 66];
let sorter = RadixSort::<i64>::new(RadixDataType::SignedInteger, SortDirection::Ascending);
sorter.sort(&mut numbers);
assert_eq!(numbers, vec![-9000, -45, 2, 24, 66, 75, 170, 802]);§Sorting Floating-Point Numbers
use universal_radix_sort::{RadixSort, RadixDataType, SortDirection};
let mut doubles = vec![3.14, -1.25, 0.5, f64::NAN, -99.9];
let sorter = RadixSort::<f64>::new(RadixDataType::Float, SortDirection::Ascending);
sorter.sort(&mut doubles);
// NaN values are placed at the end§Sorting Strings
use universal_radix_sort::{RadixSort, RadixDataType, SortDirection};
let mut fruits = vec!["banana".to_string(), "apple".to_string(), "cherry".to_string()];
let sorter = RadixSort::<String>::new(RadixDataType::String, SortDirection::Ascending);
sorter.sort(&mut fruits);
assert_eq!(fruits, vec!["apple".to_string(), "banana".to_string(), "cherry".to_string()]);§Performance & Complexity
| Metric | Complexity | Description |
|---|---|---|
| Time | O(n·k) | Where n is collection length and k is the number of passes (bytes) |
| Space | O(n) | Requires a temporary buffer of size n for stability |
§Comparison with Standard Sorts
For large n, Radix Sort is generally faster than QuickSort (O(n log n)), provided that k (the size of the data type in bytes) is not excessively large compared to log n.
- Integers/Floats: Uses 64-bit (8 bytes) or 32-bit (4 bytes) passes
- Strings: Complexity depends on the length of the longest string in the dataset
§Technical Details
- Integers: Uses an offset binary approach (flipping the sign bit) to correctly sort negative numbers before positives without branching comparisons
- Floats: Converts floating-point to integer bits. For negative floats, the bit order is inverted to preserve natural ordering when treated as integers (IEEE 754 compliant)
- Strings: Uses MSD (Most Significant Digit) first sorting strategy for lexicographical order
§Safety & Edge Cases
- NaN Handling: NaN values are consistently placed at the end of sorted collections
- Infinity: Positive and negative infinity are handled correctly per IEEE 754
- Empty Collections: Returns immediately without allocation
- Single Element: Returns immediately (already sorted)
§License
MIT License. See the LICENSE file for details.
Re-exports§
pub use enums::ProcessingOrder;pub use enums::RadixDataType;pub use enums::SortDirection;pub use error::RadixError;pub use error::RadixResult;pub use radix::RadixSort;pub use traits::RadixSortable;