FYI, Benchmark.pm has proved every guess of mine wrong in this thread:

• Using blocks in map didn't make anything slower (I didn't investigate why).
• The "map" solution is much slower than the "splice" solution unless nearly half of the elements are removed (due to overhead in executing so many Perl statements).
• chromatic's solution is slower still (which I thought would be close in speed to the "splice" solution, if not faster). I think this is because the "sort" has to be done on so many more elements.

But then that is why Benchmark was written.

        - tye (but my friends call me "Tye")