The reason Rust has a separate `sort_by_cached_key` is, of course, that it doesn’t make sense to cache cheap projections which are the 95% use case.

The implementation is somewhat more sophisticated than just the naive transform:

> The current implementation is based on instruction-parallel-network sort by Lukas Bergdoll, which combines the fast average case of randomized quicksort with the fast worst case of heapsort, while achieving linear time on fully sorted and reversed inputs. And O(k * log(n)) where k is the number of distinct elements in the input. It leverages superscalar out-of-order execution capabilities commonly found in CPUs, to efficiently perform the operation.

> In the worst case, the algorithm allocates temporary storage in a Vec<(K, usize)> the length of the slice.

Indeed, that works the same as the default C# sort: https://play.rust-lang.org/?version=stable&mode=debug&editio...