In Perl, the fastest watermark algorithm is probably

sub top_x {
    my $n = shift;
    my @top = splice @_, 0, $n;
    @top = ( sort { $a <=> $b } $_, @top )[ 1 .. $n ] for @_;
    return @top;
}
[download]

With the mergesort used in newer versions of Perl and @top being nearly sorted in all iterations but the first, sort will do its work rapidly. That will almost certainly beat any explicitly spelled out algorithm except for truly large values of $n and even longer lists (like maybe selecting the top 10,000 out of 1,000,000 elements; maybe not even that). Though I'm not sure it even beats a straight sort+slice… achieving that probably requires a list of a few thousand elements.

I had a similar wakeup call when I tried to use a heap to compete against a splice algorithm a while ago. (I can't be bothered to Super Search it right now.)

If someone cares to benchmark this, I'd very interested to see how the numbers look in practice.

It is sometimes frustrating, but clever Perl algorithms can very rarely beat builtins. If you want competitive algorithmic elegance, you'll have to drop back to XS. An XS call has a certain fixed overhead cost though so for small lists you might still lose.

Makeshifts last the longest.