well, actually Sort::Key uses the internal perl sort function under the hood. It just exposes a different API that can cover most sorting usages without incurring in an extra cost as core sort does.

The algorithm used is similar to...

 sub sortkey {
     my ($func, @v);
     my @keys = map { &$func } @v;
     my @ix = sort { $keys[$a] cmp $keys[$b] } 0..$#keys;
     return @v[@ix]
 }
[download]

but being implemented in C (specially, the comparing callbacks) it doesn't require the nasty hacks of the GRT to do the sort part efficiently.