As long as grep doesn't change the order of 0..$#allrefs, I'd expect the result to be in the same order as by the OP.

It wouldn't of course. You are right; I grossly misread ikegami's code thinking that he was iterating over the unsorted result of keys (%keep), when in fact he was iterating over the indicies of the original array. (Sorry, ikegami, I should've known better!) And the rest of this node has nothing to do with that.

At least my own mistake did encourage me to do some potentially enlightening benchmarking. It's always interesting to me when even though O(N) beats O(N log N) on a graph when N is large, how large N needs to be depends on the smaller powers of the function (never shown in big-O notation, big-Theta, yes). The bigger the constant, the bigger N must be to overcome it for the "faster" algorithm to win out, especially in Perl, which as I found out years ago, has some pretty huge constants in even the simplest of operations (but much smaller constants for many of the more complex operations like sort, which are heavily optimized in C).

What I'm saying is, performance is cute, performance is fun, and performance is often irrelevant (within a few orders of magnitude, anyway), but for me personally, obtaining surprising results about performance is one thing that played a significant part in pushing me to learn how to write better Perl code, and not just more C code translated to run in the perl interpreter.