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.

Table of Contents

• How It Works
• Installation
• API Reference
  • thanos_sort(&mut Vec<T>) -> Vec<Vec<T>>
  • thanos_sort_owned(&[T]) -> (Vec<T>, Vec<Vec<T>>)
• Usage Examples
  • Basic Sorting
  • Preserving Original Data
  • Analyzing the Elimination Process
  • Visualization
  • Working with Custom Types
  • Batch Processing
• Algorithm Details
• Testing
• Why Use This Crate?
• Why NOT Use This Crate

How It Works

Thanos Sort implements a "perfectly balanced" elimination strategy:

1. Start with a full vector of elements
2. While more than 1 element remains:
   • Calculate how many to keep: ceil(n/2) (snap away floor(n/2) elements)
   • Shuffle the remaining elements randomly
   • Truncate to keep only the first ceil(n/2) elements
   • Record the new state in history
3. End when only 1 (or 0) elements remain

Installation

Add this to your Cargo.toml:

[dependencies]
thanos-sort = "0.1.0"

API Reference

thanos_sort(&mut Vec<T>) -> Vec<Vec<T>>

What it takes:

• A mutable reference to a Vec<T> - it will modify your original vector!

What it returns:

• History: Vec<Vec<T>> - A vector of vectors showing the state after each "snap"
  • Index 0: Original state
  • Index 1: After 1st snap
  • Index 2: After 2nd snap
  • ... until final state (1 element)

Example:

use thanos_sort::thanos_sort;

let mut my_data = vec![10, 20, 30, 40, 50, 60];
let history = thanos_sort(&mut my_data);

// The mutated original vector - now only has 1 survivor!
println!("Survivor: {:?}", my_data);  // e.g., [30]

// The history - all intermediate states
for (i, state) in history.iter().enumerate() {
    println!("After snap {}: {:?} ({} elements)", i, state, state.len());
}
// Output:
// After snap 0: [10, 20, 30, 40, 50, 60] (6 elements)
// After snap 1: [60, 30, 40] (3 elements)  - shuffled + truncated
// After snap 2: [40, 30] (2 elements)
// After snap 3: [30] (1 element)

thanos_sort_owned(&[T]) -> (Vec<T>, Vec<Vec<T>>)

What it takes:

• A slice &[T] - your original data is not modified

What it returns:

• Tuple containing:
  1. Survivor: Vec<T> - The final survivor(s) (0 or 1 elements)
  2. History: Vec<Vec<T>> - Same as above, all intermediate states

Example:

use thanos_sort::thanos_sort_owned;

let original = vec![10, 20, 30, 40, 50, 60];
let (survivor, history) = thanos_sort_owned(&original);

// Original is untouched
println!("Original: {:?}", original);  // [10, 20, 30, 40, 50, 60]

// You get the survivor separately
println!("Survivor: {:?}", survivor);  // e.g., [30]

// Plus the full history
println!("History length: {}", history.len());  // 4 snaps

Usage Examples

Basic Sorting

use thanos_sort::thanos_sort;

let mut numbers = vec![4, 2, 7, 1, 9, 3];
let history = thanos_sort(&mut numbers);

assert_eq!(numbers.len(), 1);
assert_eq!(history.len(), 4); // 6 -> 3 -> 2 -> 1

Preserving Original Data

use thanos_sort::thanos_sort_owned;

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

// Original is preserved
assert_eq!(original, vec![1, 2, 3, 4, 5]);
// Survivor is the result
assert_eq!(survivor.len(), 1);
// History tracks all snaps
assert_eq!(history.len(), 4); // 5 -> 3 -> 2 -> 1

Analyzing the Elimination Process

use thanos_sort::thanos_sort;

let mut players = vec!["Thanos", "Iron Man", "Thor", "Captain America", "Hulk"];
let history = thanos_sort(&mut players);

// Who survived?
println!("The chosen one: {}", players[0]);

// Who got snapped at each stage?
for (snap, survivors) in history.iter().enumerate() {
    let snapped = if snap == 0 { 
        "Initial roster".to_string() 
    } else {
        let previous = &history[snap - 1];
        let eliminated: Vec<_> = previous.iter()
            .filter(|&p| !survivors.contains(p))
            .collect();
        format!("Snapped: {:?}", eliminated)
    };
    println!("Round {}: {:?} - {}", snap, survivors, snapped);
}

Visualization

use thanos_sort::thanos_sort_owned;

fn visualize_thanos_sort<T: std::fmt::Debug>(data: &[T]) {
    let (survivor, history) = thanos_sort_owned(data);
    
    println!("📊 Thanos Sort Visualization");
    println!("━━━━━━━━━━━━━━━━━━━━━━━━━");
    
    for (i, state) in history.iter().enumerate() {
        let bar = "█".repeat(state.len());
        let snap_info = if i == 0 { 
            "START".to_string() 
        } else {
            format!("SNAP {} (kept {}/{})", i, state.len(), history[i-1].len())
        };
        println!("{:10} │ {:<10} │ {:?}", snap_info, bar, state);
    }
    
    println!("\n🏆 SURVIVOR: {:?}", survivor);
}

// Usage
let data = vec![10, 20, 30, 40, 50, 60];
visualize_thanos_sort(&data);

Working 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 },
    Titan { name: "Thor".into(), power: 90 },
];

let (survivor, history) = thanos_sort_owned(&titans);
println!("The strongest survives: {:?}", survivor[0]);
println!("Total snaps: {}", history.len() - 1); // 3 snaps: 4 -> 2 -> 1

Batch Processing

use thanos_sort::thanos_sort_owned;

let datasets = vec![
    vec![1, 2, 3],
    vec![4, 5, 6, 7],
    vec![8, 9],
];

let results: Vec<_> = datasets.iter()
    .map(|d| thanos_sort_owned(d))
    .collect();

for (i, (survivor, history)) in results.iter().enumerate() {
    println!("Dataset {}: {} elements → {} snaps → survivor: {:?}", 
        i, 
        datasets[i].len(), 
        history.len() - 1,
        survivor
    );
}

Algorithm Details

Snap Count Behavior

Perfectly balanced, as all things should be:

Time Complexity

• Best case: O(1) - already has 0 or 1 elements
• Average case: O(n log n) - each snap halves the dataset
• Worst case: O(n log n) - same as average

Space Complexity

• With thanos_sort: O(n log n) - storing history of all states
• With thanos_sort_owned: O(n log n) - same, plus a copy of original

Testing

Run the test suite:

cargo test

This includes:

• Unit tests for edge cases
• Doctests for documentation examples
• Property-based tests for snap counts

Why Use This Crate?

✅ Educational: Demonstrates random algorithms and ownership in Rust
✅ Humorous: Perfect for code reviews and presentations
✅ Visualization: History tracking makes it great for visualizations
✅ Idiomatic: Follows Rust best practices (even though it's a joke)
✅ Well-tested: Comprehensive test suite

Why NOT Use This Crate

❌ NOT A REAL SORTING ALGORITHM - It doesn't actually sort anything
❌ DESTRUCTIVE - Eliminates data randomly
❌ NON-DETERMINISTIC - Results vary between runs
❌ INEFFICIENT - O(n log n) for no benefit
❌ USELESS - Unless you need to randomly eliminate half your data

Use data.sort_unstable() instead.

License

MIT © 2026

"Perfectly balanced, as all things should be." - Thanos