Matching Puzzle Pieces and Disappointing Benchmarks

I recently had a piece of code that used .to_lowercase() to sort some text. Which takes a bit of memory. On the plus side, the code used .sort_by_cached_key, which is pretty cool. But I wondered whether doing the .to_lowercase() log(n) times instead of n times would be slower than allocating a String for each entry, given that for many strings, even the first few charactes would be different.