`<[T]>::sort_by_index` and `<[T]>::sort_by_key_and_index`

zackw:

I feel like there ought to be a way to detect missing values (or, equivalently, duplicates) in O(1) space

If you can stomach requiring mutable access to the permutation, you could use the slice itself for the necessary memory. For &mut [usize] to be a valid permutation, each element must have a zero MSB. Using those as an N-element bitset, you could check the permutation in O(N) time and no additional space.