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

scottmcm:

I don't know a great (non-allocating) way to check that something is a permutation, though, for a safe API...

An array of integers of length N defines a permutation if and only if each of the integers 0..N appears in the array exactly once. It's obviously easy to check for integers outside the valid range. The pigeonhole principle says that if all the array entries are in the range, and there are no missing values, then there cannot be any duplicates either. I feel like there ought to be a way to detect missing values (or, equivalently, duplicates) in O(1) space but I can't think of one off the top of my head ... can we use the sum and/or product of the values somehow?