1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
use std::collections::HashMap;
use std::hash::Hash;
pub fn sort_permutation<T: Eq + Hash + Copy, V>(
values: &mut [V],
keys: &[T],
sort: impl FnOnce(&[T]) -> Vec<T>,
) {
debug_assert_eq!(
values.len(),
keys.len(),
"values and keys must have the same length",
);
if values.len() <= 1 {
return;
}
let sorted_keys = sort(keys);
// Build a map from key to its target position in the sorted order
let key_to_target_idx: HashMap<T, usize> = sorted_keys
.into_iter()
.enumerate()
.map(|(idx, key)| (key, idx))
.collect();
// Build permutation: perm[i] = where element at index i should go
let mut perm: Vec<usize> = keys.iter().map(|k| key_to_target_idx[k]).collect();
// Apply permutation in-place using cycle sort
// Example:
// keys: [K1, K3, K0, K2]
// sorted_keys: [K0, K1, K2, K3]
// perm: [1, 3, 0, 2]
for i in 0..perm.len() {
// Example step 1:
// i = 0, perm[0] = 1
// swap perm[0] and perm[1] -> [K3, K1, K0, K2]
// i = 0, perm[0] = 3
// swap perm[0] and perm[3] -> [K2, K1, K0, K3]
// i = 0, perm[0] = 2
// swap perm[0] and perm[2] -> [K0, K1, K2, K3]
while perm[i] != i {
let target = perm[i];
values.swap(i, target);
perm.swap(i, target);
}
}
}