thanos_sort/lib.rs
1//! # Thanos Sort 🗿
2//!
3//! **⚠️ WARNING: THIS CRATE IS A JOKE. DO NOT USE FOR ACTUAL SORTING.⚠️**
4//!
5//! Thanos Sort "sorts" by repeatedly snapping away half the elements until one survivor remains.
6//! Perfectly balanced, as all things should be.
7//!
8//! # Examples
9//!
10//! Basic usage with mutable reference:
11//! ```
12//! let mut data = vec![1, 2, 3, 4, 5];
13//! let history = thanos_sort::thanos_sort(&mut data);
14//!
15//! // Only one survivor remains
16//! assert_eq!(data.len(), 1);
17//! // History tracks each snap
18//! assert_eq!(history.len(), 4); // 5 -> 3 -> 2 -> 1
19//! ```
20//!
21//! If you need to keep the original data:
22//! ```
23//! let original = vec![1, 2, 3, 4, 5];
24//! let (survivor, history) = thanos_sort::thanos_sort_owned(&original);
25//!
26//! // Original is unchanged
27//! assert_eq!(original.len(), 5);
28//! // Survivor is the result
29//! assert_eq!(survivor.len(), 1);
30//! ```
31//!
32//! **Use `data.sort_unstable()` instead.**
33
34use rand::seq::SliceRandom;
35
36/// Thanos sorts by randomly halving the array until one survivor remains.
37///
38/// This function mutates the input slice in-place, destroying half of the elements
39/// (rounded down) at each iteration until only one remains. It returns a history
40/// of all intermediate states.
41///
42/// **THIS IS A JOKE. DO NOT USE FOR REAL SORTING.**
43///
44/// # Arguments
45///
46/// * `data` - A mutable reference to a `Vec<T>` to be "sorted"
47///
48/// # Returns
49///
50/// * `Vec<Vec<T>>` - History of the vector's state after each snap (including initial state)
51///
52/// # Examples
53///
54/// Basic sorting:
55/// ```
56/// use thanos_sort::thanos_sort;
57///
58/// let mut numbers = vec![4, 2, 7, 1, 9, 3];
59/// let history = thanos_sort(&mut numbers);
60///
61/// // Only one number survives
62/// assert_eq!(numbers.len(), 1);
63/// // We can see the whole history
64/// assert_eq!(history.len(), 4); // 6 -> 3 -> 2 -> 1
65/// ```
66///
67/// Empty vector:
68/// ```
69/// use thanos_sort::thanos_sort;
70///
71/// let mut empty: Vec<i32> = vec![];
72/// let history = thanos_sort(&mut empty);
73///
74/// assert!(empty.is_empty());
75/// assert_eq!(history.len(), 1);
76/// assert!(history[0].is_empty());
77/// ```
78///
79/// Single element (no snaps needed):
80/// ```
81/// use thanos_sort::thanos_sort;
82///
83/// let mut data = vec![42];
84/// let history = thanos_sort(&mut data);
85///
86/// assert_eq!(data, vec![42]);
87/// assert_eq!(history.len(), 1);
88/// ```
89///
90/// Works with any cloneable type:
91/// ```
92/// use thanos_sort::thanos_sort;
93///
94/// let mut strings = vec!["thanos".to_string(), "sort".to_string(), "is".to_string(), "balanced".to_string()];
95/// let history = thanos_sort(&mut strings);
96///
97/// assert_eq!(strings.len(), 1);
98/// assert_eq!(history.len(), 3); // 4 -> 2 -> 1
99/// ```
100pub fn thanos_sort<T>(data: &mut Vec<T>) -> Vec<Vec<T>>
101where
102 T: Clone,
103{
104 let mut history = vec![data.clone()];
105
106 while data.len() > 1 {
107 let keep_count = data.len().div_ceil(2);
108 let mut rng = rand::rng();
109 data.shuffle(&mut rng);
110 data.truncate(keep_count);
111 history.push(data.clone());
112 }
113
114 history
115}
116
117/// Owned version of Thanos sort that preserves the original data.
118///
119/// This function takes a slice and returns both the survivor vector and the history,
120/// leaving the original data untouched. Useful when you need to keep the original
121/// collection for other purposes.
122///
123/// **THIS IS A JOKE. DO NOT USE FOR REAL SORTING.**
124///
125/// # Arguments
126///
127/// * `data` - A slice of `T` to be "sorted"
128///
129/// # Returns
130///
131/// * `(Vec<T>, Vec<Vec<T>>)` - A tuple containing:
132/// * The survivor vector (single element or empty)
133/// * History of all intermediate states
134///
135/// # Examples
136///
137/// Basic usage:
138/// ```
139/// use thanos_sort::thanos_sort_owned;
140///
141/// let original = vec![10, 20, 30, 40, 50];
142/// let (survivor, history) = thanos_sort_owned(&original);
143///
144/// // Original is preserved
145/// assert_eq!(original, vec![10, 20, 30, 40, 50]);
146/// // Survivor is the result
147/// assert_eq!(survivor.len(), 1);
148/// // History tracks all snaps
149/// assert_eq!(history.len(), 4); // 5 -> 3 -> 2 -> 1
150/// ```
151///
152/// Empty slice:
153/// ```
154/// use thanos_sort::thanos_sort_owned;
155///
156/// let empty: &[i32] = &[];
157/// let (survivor, history) = thanos_sort_owned(empty);
158///
159/// assert!(survivor.is_empty());
160/// assert_eq!(history.len(), 1);
161/// assert!(history[0].is_empty());
162/// ```
163///
164/// Single element:
165/// ```
166/// use thanos_sort::thanos_sort_owned;
167///
168/// let (survivor, history) = thanos_sort_owned(&[99]);
169///
170/// assert_eq!(survivor, vec![99]);
171/// assert_eq!(history.len(), 1);
172/// ```
173///
174/// Works with custom types:
175/// ```
176/// use thanos_sort::thanos_sort_owned;
177///
178/// #[derive(Debug, Clone, PartialEq)]
179/// struct Titan {
180/// name: String,
181/// power: u32,
182/// }
183///
184/// let titans = vec![
185/// Titan { name: "Thanos".into(), power: 100 },
186/// Titan { name: "Star Lord".into(), power: 50 },
187/// Titan { name: "Gamora".into(), power: 75 },
188/// ];
189///
190/// let (survivor, history) = thanos_sort_owned(&titans);
191///
192/// assert_eq!(survivor.len(), 1);
193/// assert_eq!(history.len(), 3); // 3 -> 2 -> 1
194/// assert_eq!(titans.len(), 3); // Original unchanged
195/// ```
196pub fn thanos_sort_owned<T: Clone>(data: &[T]) -> (Vec<T>, Vec<Vec<T>>) {
197 let mut data = data.to_vec();
198 let history = thanos_sort(&mut data);
199 (data, history)
200}
201
202#[cfg(test)]
203mod tests {
204 use super::*;
205
206 #[test]
207 fn test_even_length() {
208 let mut data = vec![1, 2, 3, 4];
209 let history = thanos_sort(&mut data);
210 assert_eq!(data.len(), 1);
211 assert_eq!(history[0].len(), 4);
212 assert_eq!(history[1].len(), 2);
213 }
214
215 #[test]
216 fn test_odd_length() {
217 let mut data = vec![1, 2, 3];
218 let history = thanos_sort(&mut data);
219 assert_eq!(data.len(), 1);
220 assert_eq!(history[0].len(), 3);
221 assert_eq!(history[1].len(), 2);
222 assert_eq!(history[2].len(), 1);
223 }
224
225 #[test]
226 fn test_single_element() {
227 let mut data = vec![42];
228 let history = thanos_sort(&mut data);
229 assert_eq!(data, vec![42]);
230 assert_eq!(history.len(), 1);
231 }
232
233 #[test]
234 fn test_empty() {
235 let mut data: Vec<i32> = vec![];
236 let history = thanos_sort(&mut data);
237 assert!(data.is_empty());
238 assert_eq!(history.len(), 1);
239 assert!(history[0].is_empty());
240 }
241
242 #[test]
243 fn test_snap_counts() {
244 let test_cases = vec![
245 (1, vec![1]),
246 (2, vec![2, 1]),
247 (3, vec![3, 2, 1]),
248 (4, vec![4, 2, 1]),
249 (5, vec![5, 3, 2, 1]),
250 (6, vec![6, 3, 2, 1]),
251 (7, vec![7, 4, 2, 1]),
252 (8, vec![8, 4, 2, 1]),
253 ];
254
255 for (start_len, expected_lengths) in test_cases {
256 let mut data: Vec<i32> = vec![0; start_len];
257 let history = thanos_sort(&mut data);
258 let actual_lengths: Vec<usize> = history.iter().map(|v| v.len()).collect();
259 assert_eq!(
260 actual_lengths, expected_lengths,
261 "Failed for length {}: expected {:?}, got {:?}",
262 start_len, expected_lengths, actual_lengths
263 );
264 }
265 }
266
267 #[test]
268 fn test_owned_version_preserves_original() {
269 let original = vec![1, 2, 3, 4, 5];
270 let (survivor, history) = thanos_sort_owned(&original);
271
272 assert_eq!(original.len(), 5);
273 assert_eq!(survivor.len(), 1);
274 assert_eq!(history.len(), 4);
275 }
276
277 #[test]
278 fn test_with_strings() {
279 let mut data = vec!["a".to_string(), "b".to_string(), "c".to_string()];
280 let _history = thanos_sort(&mut data);
281 assert_eq!(data.len(), 1);
282 }
283}