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
• Installation
• Quick Start
• Performance & Complexity
• When to Use Radix Sort
• Technical Details
• API Documentation
• Safety & Edge Cases
• Benchmarking
• Contributing
• License

Features

Installation

Add this to your Cargo.toml:

[dependencies]
universal_radix_sort = "0.1.0"

Or install via cargo:

cargo add universal_radix_sort

Quick Start

Sorting Integers

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

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.

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.

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

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

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

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.

When to Use Radix Sort

Good For

Not Ideal For

Break-Even Point

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:

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

Floating-Point Sorting

Converts double to int bits using IEEE 754 transformation:

// 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

Full Documentation

Visit docs.rs/universal_radix_sort for complete API documentation with examples.

Safety & Edge Cases

Example: NaN Handling

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

# 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

# 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
• 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)