In Perl, you can use my module Sort::Key::Top to select the top n elements from a list. For instance, to get the median from a list of numbers:

use List::Util qw(shuffle max);
use Sort::Key::Top qw(ntop);
my @data = shuffle (0..100);
my $mediam = ntop -1, ntop 1 + @data / 2, @data; # O(N)
# or
# $mediam = max ntop 1 + @data / 2, @data; # O(N)
# $mediam = (ntopsort 1 + @data / 2, @data)[-1]; # O(NlogN)!
print "mediam: $mediam\n";
[download]

ntopsort returns them sorted, but it has O(NlogN) complexity.

update: BTW, the n in ntop doesn't stand for nth but for numeric!

Note how you can find the median asymptotically faster than do a half-sort. Indeed, the c++ stdlib has functions both for half-sort and for median.

If you want to find the median fast, see Re: Puzzle: The Ham Cheese Sandwich cut. and other nodes in its thread (that thread has an easy to remember title). If you want to do a half-sort with a heap, see Binary heap, but it actually also works to just find the median, partition the elements to ones greater and lessequal to it, and then sort one of the halves.

While reading it I was reminded of a rather interesting thread on p5p regarding heap sort.

Short summary: some research folks found that they could reduce the number of comparisons in heapsort. John P. Linderman answered that it's all fine and good, but in real life heapsort suffers from bad caching characteristics, and thus can't really compete with mergesort and quicksort.

Still it's a very nice technique, and I could imagine that heapsort beats other algorithms when you only need to sort half of the list. (Maybe you could also optimize quicksort to only find the median - any thoughts on that?)

I'd like to say that, as a perl guy without a comp sci background, the only places I get this sort of information are Mastering Algorithms in Perl and nodes like these here, so I really appreciate them. Off to Wikipedia to read more, I suppose.

"(Note that "heap" can also refer to an area of memory used for dynamic memory allocation.)" - This was useful because I came in here expecting databases stored in memory, and you were starting to weird me out talking about btrees :).

I added that remark about the other meaning of "heap" after feedback from moritz, who was among several monks who helpfully reviewed this meditation before I posted it. A big thanks also should go to tye.

• Make sure Heap::Simple::XS is used if you care about speed for this kind of operation.
• Use the (default) scalar element type if that is good enough. It's the fastest of the available element types.
• Use the max_count option if you only want an already known last m elements. This will save a lot of compares. In this case it also saves the extract loop.

You can also add the dirty option. Heap::Simple::XS will then use direct numeric compares instead of calling perl's >. This breaks overload and ties though. That way the Heap::Simple solution is about twice as fast as sort. The break-even is somewhere in the ten thousands of elements.

The resulting code looks something like this:

use List::Util qw(shuffle);
use POSIX qw(ceil);
use Heap::Simple::XS;

my @list = shuffle(0..1e6); 
my $h = Heap::Simple::XS->new(max_count => ceil(@list/2),
                              dirty => 1);
$h->insert(@list);
print $h->extract_top;
[download]

This doesn't change the fact that for even quite big lists sort is just faster for this kind of problem. Heaps are mainly for when you need to know the smallest element at many points in time while the set of elements keeps changing. Or indeed for some cases where compare is very expensive, but even then there are better ways to do it with less compares if you just want the median.

PS: Heap::Simple already uses special code to make an insert of many elements at once faster than repeatedly inserting one element. You seem to hint at an even faster algorithm but I don't see how to use Tarjan's algorithm for that. Can you give me a reference ?

Thanks for your comments!

I'm sorry to say I don't know any more about building heaps faster than the little bit I said in the article. I got what I wrote about Tarjan's algorithm from the Wikipedia article, Heap (data structure), but I haven't looked into it myself at all. Sorry I can't be more help.

Sorry, didn't read till the end of the article before posting the above. Anyway, there is no need for Tarjan's algorithm, since a tighter analysis of a simple heapify-up/heapify-down algorithm shows that it works in O(n).
As for finding the median, this can be always done in O(n) using the so called Selection algorithm. (a particular variant - randomized selection - works very fast in practice)
The only interesting problem is about having a structure such that several(many) extractions of the medians are O(log n) each, with as little overhead is possible for maintaining such a structure (under e.g. insertions of new elements).

Another recent topic here led me to this article: www.sysarch.com/Perl/sort_paper.html. It shows that of two seemingly identical sorts:

@fast = sort @unsorted;
@slow = sort { $a <=> $b } @unsorted;
[download]

The first one is faster because it runs entirely in C in the Perl core, while the second is slower because the sortsub executes in Perl code.

I was sorting tens of thousands of files by creation time in reverse chronological order, and was delighted to find the first one below faster than the second:

@fast = reverse sort @unsorted;
@slow = sort { $b <=> $a } @unsorted;
[download]

kyle, I wonder how your median_sort might benchmark if it used my @s = sort @_;?

I'll start by pointing out that the two sorts you show are not identical.

use List::Util qw( shuffle );

my @n = shuffle 5 .. 15;
print join( q{, }, sort @n ), "\n";
print join( q{, }, sort { $a <=> $b } @n ), "\n";
__END__
10, 11, 12, 13, 14, 15, 5, 6, 7, 8, 9
5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
[download]

That's because sort, by default, uses "cmp" rather than "<=>" for comparisons. That's sort of beside your point, however. A sort with the comparison unspecified will be faster than one that's explicit, and there's a convenient special case for "reverse sort". That's all good.

It's sort of beside the point of my meditation, however. The point here was to compare efficiency and speed. With the tied scalars, I was able to show that the heap method was more efficient—it did fewer comparisons. In spite of that, it was still slower because sort does its comparisons so much faster due to being optimized C.

In any case, thanks for your comment.