universal_radix_sort 1.0.0

# 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.

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.

## Table of Contents

- [Features](#features)
- [Installation](#installation)
- [Quick Start](#quick-start)
- [Performance & Complexity](#performance--complexity)
- [When to Use Radix Sort](#when-to-use-radix-sort)
- [Technical Details](#technical-details)
- [API Documentation](#api-documentation)
- [Safety & Edge Cases](#safety--edge-cases)
- [Benchmarking](#benchmarking)
- [Contributing](#contributing)
- [License](#license)

## Features

| Feature | Description |
|---------|-------------|
| **Fast** | Linear time complexity O(n·k) where k is the number of bytes/digits |
| **Universal** | Supports `i8`-`i128`, `u8`-`u128`, `f32`, `f64`, `String`, and `&str` |
| **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 |
| **Stable Sort** | Maintains relative order of equal elements |

## Installation

Add this to your `Cargo.toml`:

```toml
[dependencies]
universal_radix_sort = "0.1.0"
```

Or install via cargo:

```bash
cargo add universal_radix_sort
```

## Quick Start

### Sorting Integers

Handles signed integers correctly using bit manipulation to map them to an unsigned space.

```rust
use universal_radix_sort::{RadixSort, RadixDataType, SortDirection};

fn main() {
    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).unwrap();
    
    println!("{:?}", numbers);
    // Output: [-9000, -45, 2, 24, 66, 75, 170, 802]
}
```

### Sorting Floating-Point Numbers

Handles floating-point intricacies (negative zero, denormalized numbers, NaN) via IEEE 754 bit-flipping logic.

```rust
use universal_radix_sort::{RadixSort, RadixDataType, SortDirection};

fn main() {
    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).unwrap();
    
    // NaN values are placed at the end
    println!("{:?}", doubles);
    // Output: [-99.9, -1.25, 0.5, 3.14, NaN]
}
```

### Sorting Strings

Uses lexicographical ordering with MSD (Most Significant Digit) first strategy.

```rust
use universal_radix_sort::{RadixSort, RadixDataType, SortDirection};

fn main() {
    let mut fruits = vec![
        "banana".to_string(),
        "apple".to_string(),
        "cherry".to_string(),
        "date".to_string(),
    ];
    let sorter = RadixSort::<String>::new(
        RadixDataType::String,
        SortDirection::Ascending,
    );
    sorter.sort(&mut fruits).unwrap();
    
    println!("{:?}", fruits);
    // Output: ["apple", "banana", "cherry", "date"]
}
```

### Descending Order

```rust
use universal_radix_sort::{RadixSort, RadixDataType, SortDirection};

fn main() {
    let mut numbers = vec![5, 2, 8, 1, 9];
    let sorter = RadixSort::<i64>::new(
        RadixDataType::SignedInteger,
        SortDirection::Descending,
    );
    sorter.sort(&mut numbers).unwrap();
    
    println!("{:?}", numbers);
    // Output: [9, 8, 5, 2, 1]
}
```

### Return New Sorted Vector

```rust
use universal_radix_sort::RadixSort;

fn main() {
    let numbers = vec![5, 2, 8, 1, 9];
    let sorter = RadixSort::<i64>::default();
    let sorted = sorter.sort_to_vec(&numbers).unwrap();
    
    println!("Original: {:?}", numbers);  // Unchanged
    println!("Sorted: {:?}", sorted);     // New sorted vector
}
```

## Performance & Complexity

| Metric | Complexity | Description |
|--------|------------|-------------|
| **Time** | O(n·k) | Where n is array 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.

| Data Type | Passes (k) | Best For |
|-----------|------------|----------|
| **Integers** | 8 bytes (64-bit) | Large numeric datasets |
| **Floats** | 8 bytes (64-bit) | Scientific computing |
| **Strings** | Variable | Fixed-length or similar-length strings |

## When to Use Radix Sort

### Good For

| Scenario | Reason |
|----------|--------|
| **Large datasets** (> 1,000 elements) | Linear complexity beats O(n log n) |
| **Fixed-width numeric types** | Predictable number of passes |
| **Stability required** | Radix Sort is inherently stable |
| **Known value ranges** | Efficient byte extraction |
| **Repeated sorting** | Consistent performance |

### Not Ideal For

| Scenario | Reason |
|----------|--------|
| **Small datasets** (< 100 elements) | Constant overhead outweighs benefits |
| **Highly variable-length strings** | k becomes unpredictable |
| **Memory constrained** | Requires O(n) temporary buffer |
| **Custom comparators** | Radix Sort uses natural ordering |
| **Linked lists** | Requires random access |

### Break-Even Point

```rust
use universal_radix_sort::utils::estimate_break_even_point;

// Estimated minimum collection size for Radix Sort to be beneficial
let break_even = estimate_break_even_point(8); // 8 bytes (i64, f64)
// Returns: ~1000 elements
```

## Technical Details

### Integer Sorting

Uses an **offset binary approach** (flipping the sign bit) to correctly sort negative numbers before positives without branching comparisons:

```rust
// Transformation for signed integers
const SIGN_BIT: u64 = 1 << 63;
let transformed = (value as u64) ^ SIGN_BIT;
```

| Original | Transformed |
|----------|-------------|
| `-9000` | Small positive |
| `-1` | Medium positive |
| `0` | Middle value |
| `1` | Large positive |
| `9000` | Larger positive |

### Floating-Point Sorting

Converts `double` to `int` bits using **IEEE 754** transformation:

| Value Type | Transformation |
|------------|----------------|
| **Positive** | Flip sign bit only |
| **Negative** | Flip ALL bits |
| **NaN** | Map to maximum key (sorted to end) |
| **Infinity** | Handled correctly per IEEE 754 |

```rust
// IEEE 754 transformation
if value.is_nan() {
    u64::MAX  // NaN goes to end
} else if bits & 0x8000_0000_0000_0000 != 0 {
    !bits  // Negative: flip all bits
} else {
    bits ^ 0x8000_0000_0000_0000  // Positive: flip sign bit
}
```

### String Sorting

Decomposes strings into **UTF-8 bytes** and applies **MSB (Most Significant Byte) first** sorting strategy for correct lexicographical order:

- Uses 256 radix (UTF-8) instead of 65536 (UTF-16) for memory efficiency
- Handles variable-length strings with null-byte padding
- Early termination optimization for MSD-first mode

## API Documentation

### Core Types

| Type | Description |
|------|-------------|
| [`RadixSort<T>`](https://docs.rs/universal_radix_sort/latest/universal_radix_sort/struct.RadixSort.html) | Main sorting struct |
| [`RadixDataType`](https://docs.rs/universal_radix_sort/latest/universal_radix_sort/enum.RadixDataType.html) | Data type configuration |
| [`SortDirection`](https://docs.rs/universal_radix_sort/latest/universal_radix_sort/enum.SortDirection.html) | Ascending/Descending |
| [`ProcessingOrder`](https://docs.rs/universal_radix_sort/latest/universal_radix_sort/enum.ProcessingOrder.html) | LSB-first/MSB-first |
| [`RadixSortable`](https://docs.rs/universal_radix_sort/latest/universal_radix_sort/trait.RadixSortable.html) | Trait for sortable types |
| [`RadixError`](https://docs.rs/universal_radix_sort/latest/universal_radix_sort/enum.RadixError.html) | Error types |

### Full Documentation

Visit [docs.rs/universal_radix_sort](https://docs.rs/universal_radix_sort) for complete API documentation with examples.

## Safety & Edge Cases

| Edge Case | Handling |
|-----------|----------|
| **NaN values** | Consistently placed at the end |
| **Infinity** | Positive/Negative infinity handled per IEEE 754 |
| **Negative zero** | Treated equal to positive zero |
| **Empty collections** | Returns immediately without allocation |
| **Single element** | Returns immediately (already sorted) |
| **Duplicates** | Maintains stability (relative order preserved) |
| **Empty strings** | Sorted before non-empty strings |

### Example: NaN Handling

```rust
use universal_radix_sort::{RadixSort, RadixDataType};

let mut values = vec![3.14f64, f64::NAN, -1.25, 0.5];
let sorter = RadixSort::<f64>::new(RadixDataType::Float, SortDirection::Ascending);
sorter.sort(&mut values).unwrap();

assert!(values[3].is_nan());  // NaN at the end
assert_eq!(&values[..3], &[-1.25, 0.5, 3.14]);
```

## Benchmarking

### Run Benchmarks

```bash
# Run all benchmarks
cargo bench

# Run specific benchmark group
cargo bench --bench benchmark -- Integer

# View HTML report
open target/criterion/report/index.html
```

### Benchmark Suite

The included benchmark suite compares Radix Sort against Rust's standard library sort:

- **Integer Sorting**: `i64` with various dataset sizes
- **Float Sorting**: `f64` with NaN and Infinity handling
- **String Sorting**: Variable-length strings

### Performance Tips

1. **Use release mode** for accurate benchmarks: `cargo bench --release`
2. **Run multiple times** to average out system noise
3. **Close other applications** to reduce CPU contention
4. **Monitor thermal throttling** on laptops

## Contributing

Contributions are welcome! Please follow these guidelines:

### Getting Started

```bash
# Fork the repository
git clone https://codeberg.org/ios-community/universal-radix-sort.git
cd universal_radix_sort

# Run tests
cargo test

# Run benchmarks
cargo bench
```

### Code Style

- Follow [Rust API Guidelines](https://rust-lang.github.io/api-guidelines/)
- Include documentation comments with examples
- Add tests for new functionality
- Run `cargo clippy` and `cargo fmt` before submitting

### Pull Request Checklist

- [ ] Tests pass (`cargo test`)
- [ ] Benchmarks run (`cargo bench`)
- [ ] Documentation updated
- [ ] Clippy warnings resolved
- [ ] Code formatted (`cargo fmt`)