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

This MathOverflow answer seems to indicate that we do not yet have any deterministic algorithm which checks for duplicates in O(n) time and O(1) space (though we don't seem to have proven it impossible yet).