thanos_sort/

lib.rs

#![doc = include_str!("../README.md")]
#![deny(missing_docs)]
#![warn(rustdoc::missing_crate_level_docs)]

//! # Thanos Sort 🗿
//!
//! **⚠️ WARNING: THIS CRATE IS A JOKE. DO NOT USE FOR ACTUAL SORTING.⚠️**
//!
//! Thanos Sort "sorts" by repeatedly snapping away half the elements until one survivor remains.
//! Perfectly balanced, as all things should be.
//!
//! # Examples
//!
//! Basic usage with mutable reference:
//! ```
//! let mut data = vec![1, 2, 3, 4, 5];
//! let history = thanos_sort::thanos_sort(&mut data);
//!
//! // Only one survivor remains
//! assert_eq!(data.len(), 1);
//! // History tracks each snap
//! assert_eq!(history.len(), 4); // 5 -> 3 -> 2 -> 1
//! ```
//!
//! If you need to keep the original data:
//! ```
//! let original = vec![1, 2, 3, 4, 5];
//! let (survivor, history) = thanos_sort::thanos_sort_owned(&original);
//!
//! // Original is unchanged
//! assert_eq!(original.len(), 5);
//! // Survivor is the result
//! assert_eq!(survivor.len(), 1);
//! ```
//!
//! **Use `data.sort_unstable()` instead.**
extern crate self as thanos_sort;

use rand::seq::SliceRandom;

/// Thanos sorts by randomly halving the array until one survivor remains.
///
/// This function mutates the input slice in-place, destroying half of the elements
/// (rounded down) at each iteration until only one remains. It returns a history
/// of all intermediate states.
///
/// **THIS IS A JOKE. DO NOT USE FOR REAL SORTING.**
///
/// # Arguments
///
/// * `data` - A mutable reference to a `Vec<T>` to be "sorted"
///
/// # Returns
///
/// * `Vec<Vec<T>>` - History of the vector's state after each snap (including initial state)
///
/// # Examples
///
/// Basic sorting:
/// ```
/// use thanos_sort::thanos_sort;
///
/// let mut numbers = vec![4, 2, 7, 1, 9, 3];
/// let history = thanos_sort(&mut numbers);
///
/// // Only one number survives
/// assert_eq!(numbers.len(), 1);
/// // We can see the whole history
/// assert_eq!(history.len(), 4); // 6 -> 3 -> 2 -> 1
/// ```
///
/// Empty vector:
/// ```
/// use thanos_sort::thanos_sort;
///
/// let mut empty: Vec<i32> = vec![];
/// let history = thanos_sort(&mut empty);
///
/// assert!(empty.is_empty());
/// assert_eq!(history.len(), 1);
/// assert!(history[0].is_empty());
/// ```
///
/// Single element (no snaps needed):
/// ```
/// use thanos_sort::thanos_sort;
///
/// let mut data = vec![42];
/// let history = thanos_sort(&mut data);
///
/// assert_eq!(data, vec![42]);
/// assert_eq!(history.len(), 1);
/// ```
///
/// Works with any cloneable type:
/// ```
/// use thanos_sort::thanos_sort;
///
/// let mut strings = vec!["thanos".to_string(), "sort".to_string(), "is".to_string(), "balanced".to_string()];
/// let history = thanos_sort(&mut strings);
///
/// assert_eq!(strings.len(), 1);
/// assert_eq!(history.len(), 3); // 4 -> 2 -> 1
/// ```
pub fn thanos_sort<T>(data: &mut Vec<T>) -> Vec<Vec<T>>
where
    T: Clone,
{
    let mut history = vec![data.clone()];

    while data.len() > 1 {
        let keep_count = data.len().div_ceil(2);
        let mut rng = rand::rng();
        data.shuffle(&mut rng);
        data.truncate(keep_count);
        history.push(data.clone());
    }

    history
}

/// Owned version of Thanos sort that preserves the original data.
///
/// This function takes a slice and returns both the survivor vector and the history,
/// leaving the original data untouched. Useful when you need to keep the original
/// collection for other purposes.
///
/// **THIS IS A JOKE. DO NOT USE FOR REAL SORTING.**
///
/// # Arguments
///
/// * `data` - A slice of `T` to be "sorted"
///
/// # Returns
///
/// * `(Vec<T>, Vec<Vec<T>>)` - A tuple containing:
///   * The survivor vector (single element or empty)
///   * History of all intermediate states
///
/// # Examples
///
/// Basic usage:
/// ```
/// use thanos_sort::thanos_sort_owned;
///
/// let original = vec![10, 20, 30, 40, 50];
/// let (survivor, history) = thanos_sort_owned(&original);
///
/// // Original is preserved
/// assert_eq!(original, vec![10, 20, 30, 40, 50]);
/// // Survivor is the result
/// assert_eq!(survivor.len(), 1);
/// // History tracks all snaps
/// assert_eq!(history.len(), 4); // 5 -> 3 -> 2 -> 1
/// ```
///
/// Empty slice:
/// ```
/// use thanos_sort::thanos_sort_owned;
///
/// let empty: &[i32] = &[];
/// let (survivor, history) = thanos_sort_owned(empty);
///
/// assert!(survivor.is_empty());
/// assert_eq!(history.len(), 1);
/// assert!(history[0].is_empty());
/// ```
///
/// Single element:
/// ```
/// use thanos_sort::thanos_sort_owned;
///
/// let (survivor, history) = thanos_sort_owned(&[99]);
///
/// assert_eq!(survivor, vec![99]);
/// assert_eq!(history.len(), 1);
/// ```
///
/// Works with custom types:
/// ```
/// use thanos_sort::thanos_sort_owned;
///
/// #[derive(Debug, Clone, PartialEq)]
/// struct Titan {
///     name: String,
///     power: u32,
/// }
///
/// let titans = vec![
///     Titan { name: "Thanos".into(), power: 100 },
///     Titan { name: "Star Lord".into(), power: 50 },
///     Titan { name: "Gamora".into(), power: 75 },
/// ];
///
/// let (survivor, history) = thanos_sort_owned(&titans);
///
/// assert_eq!(survivor.len(), 1);
/// assert_eq!(history.len(), 3); // 3 -> 2 -> 1
/// assert_eq!(titans.len(), 3); // Original unchanged
/// ```
pub fn thanos_sort_owned<T: Clone>(data: &[T]) -> (Vec<T>, Vec<Vec<T>>) {
    let mut data = data.to_vec();
    let history = thanos_sort(&mut data);
    (data, history)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_even_length() {
        let mut data = vec![1, 2, 3, 4];
        let history = thanos_sort(&mut data);
        assert_eq!(data.len(), 1);
        assert_eq!(history[0].len(), 4);
        assert_eq!(history[1].len(), 2);
    }

    #[test]
    fn test_odd_length() {
        let mut data = vec![1, 2, 3];
        let history = thanos_sort(&mut data);
        assert_eq!(data.len(), 1);
        assert_eq!(history[0].len(), 3);
        assert_eq!(history[1].len(), 2);
        assert_eq!(history[2].len(), 1);
    }

    #[test]
    fn test_single_element() {
        let mut data = vec![42];
        let history = thanos_sort(&mut data);
        assert_eq!(data, vec![42]);
        assert_eq!(history.len(), 1);
    }

    #[test]
    fn test_empty() {
        let mut data: Vec<i32> = vec![];
        let history = thanos_sort(&mut data);
        assert!(data.is_empty());
        assert_eq!(history.len(), 1);
        assert!(history[0].is_empty());
    }

    #[test]
    fn test_snap_counts() {
        let test_cases = vec![
            (1, vec![1]),
            (2, vec![2, 1]),
            (3, vec![3, 2, 1]),
            (4, vec![4, 2, 1]),
            (5, vec![5, 3, 2, 1]),
            (6, vec![6, 3, 2, 1]),
            (7, vec![7, 4, 2, 1]),
            (8, vec![8, 4, 2, 1]),
        ];

        for (start_len, expected_lengths) in test_cases {
            let mut data: Vec<i32> = vec![0; start_len];
            let history = thanos_sort(&mut data);
            let actual_lengths: Vec<usize> = history.iter().map(|v| v.len()).collect();
            assert_eq!(
                actual_lengths, expected_lengths,
                "Failed for length {}: expected {:?}, got {:?}",
                start_len, expected_lengths, actual_lengths
            );
        }
    }

    #[test]
    fn test_owned_version_preserves_original() {
        let original = vec![1, 2, 3, 4, 5];
        let (survivor, history) = thanos_sort_owned(&original);

        assert_eq!(original.len(), 5);
        assert_eq!(survivor.len(), 1);
        assert_eq!(history.len(), 4);
    }

    #[test]
    fn test_with_strings() {
        let mut data = vec!["a".to_string(), "b".to_string(), "c".to_string()];
        let _history = thanos_sort(&mut data);
        assert_eq!(data.len(), 1);
    }
}