universal_radix_sort 1.0.0

//! Utility functions for Radix Sort operations.
//!
//! This module provides helper functions for common operations used throughout
//! the Radix Sort implementation.

/// Calculates the number of bytes needed to represent a value.
///
/// # Arguments
///
/// * `value` - The value to measure
///
/// # Returns
///
/// The number of bytes required
#[inline]
pub fn bytes_needed<T>(_: &T) -> usize {
    std::mem::size_of::<T>()
}

/// Checks if a slice is already sorted.
///
/// # Arguments
///
/// * `slice` - The slice to check
///
/// # Returns
///
/// `true` if sorted in ascending order, `false` otherwise
///
/// # Examples
///
/// ```rust
/// use universal_radix_sort::utils::is_sorted;
///
/// assert!(is_sorted(&[1, 2, 3, 4, 5]));
/// assert!(!is_sorted(&[1, 3, 2, 4, 5]));
/// ```
pub fn is_sorted<T: Ord>(slice: &[T]) -> bool {
    slice.windows(2).all(|w| w[0] <= w[1])
}

/// Checks if a slice is sorted in descending order.
///
/// # Arguments
///
/// * `slice` - The slice to check
///
/// # Returns
///
/// `true` if sorted in descending order, `false` otherwise
pub fn is_sorted_descending<T: Ord>(slice: &[T]) -> bool {
    slice.windows(2).all(|w| w[0] >= w[1])
}

/// Reverses a slice in-place.
///
/// # Arguments
///
/// * `slice` - The slice to reverse
///
/// # Examples
///
/// ```rust
/// use universal_radix_sort::utils::reverse_slice;
///
/// let mut data = vec![1, 2, 3, 4, 5];
/// reverse_slice(&mut data);
/// assert_eq!(data, vec![5, 4, 3, 2, 1]);
/// ```
pub fn reverse_slice<T>(slice: &mut [T]) {
    let mut i = 0;
    let mut j = slice.len().saturating_sub(1);
    while i < j {
        slice.swap(i, j);
        i += 1;
        if j == 0 {
            break;
        }
        j -= 1;
    }
}

/// Estimates the break-even point where Radix Sort becomes faster than QuickSort.
///
/// # Arguments
///
/// * `element_size` - Size of each element in bytes
///
/// # Returns
///
/// Estimated minimum collection size for Radix Sort to be beneficial
///
/// # Note
///
/// This is a rough estimate. Actual performance depends on many factors including
/// CPU cache, memory bandwidth, and data distribution.
pub fn estimate_break_even_point(element_size: usize) -> usize {
    // Radix Sort has higher constant factors but better asymptotic complexity
    // Break-even is typically around 100-1000 elements depending on element size
    match element_size {
        1..=4 => 500,
        5..=8 => 1000,
        _ => 2000,
    }
}