The Schwartzian Transform would work for this application, just like it would for any sort. It is a replacement for a normal sort which trades memory space for speed. For example, imagine you need to sort by the foozle() of each member of a list. You could do it the easy way:

@result = sort { foozle($a) <=> foozle($b) } @list;

But the problem is that foozle() will be called multiple times for each item being sorted. If foozle() is a slow function then you'll be wasting a lot of time. The Schwartzian transform works by building up a temporary data structure than contains the value and the foozle() of that value. Example:

@result = map { $_->[1] } 
            sort { $a->[0] <=> $b->[0] }
              map { [ foozle($_), $_ ] } 
                @list;
[download]

However, in this case the "foozle()" is just a hash lookup. Hash lookups are so fast that an ST is probably more expensive than a simple sort.

-sam