s/2%/50%/ (roughly, depending). And it isn't just the comparison routine that is the problem. Constructing a huge number of tiny arrays takes some time (and memory).
I think fast, flexible, stable sort can be rolled into a module that makes the key construction easy and natural where the module overhead is low and outside of the sorting and so using the module would give performance (in speed and memory use) on par with a very efficient hand-rolled solution and much faster than any general-purpose Perl sorting modules I've looked at.
Having sort default to sorting array references as you've specified certainly makes sense. The boring answer is that backward compatibility prevents it from happening in Perl5. I won't pretend to remember how this type of operation is likely to behave in Perl6.