1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
//! # 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`, and `String`
//! - **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`:
//!
//! ```toml
//! [dependencies]
//! universal_radix_sort = "1.0.0"
//! ```
//!
//! ## Quick Start
//!
//! ### Sorting Integers
//!
//! ```rust
//! 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
//!
//! ```rust
//! 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
//!
//! ```rust
//! 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](LICENSE) file for details.
pub use ;
pub use ;
pub use RadixSort;
pub use RadixSortable;