As ambrus said, even the warm-up problem is pretty damned hard. I too cheated by looking in Cormen, Leiserson and Rivest. Here is a Perl implementation of the linear-time algorithm they give. 
sub naive_median {
  (sort {$a <=> $b} @_)[@_/2];
}

sub nth_largest {
  my ($n, @a) = @_;
  die "You can't find the ${n}th-largest element of an ".@a."-element 
+array!"
    if $n > $#a || $n < 0;
  #warn "Looking for ${n}th element of (@a)\n";
  return $a[0] if $n == 0;

  my @medians;
  for(my $i=0; $i < @a; $i += 5) {
    push @medians, naive_median(@a[$i..($i+4 > $#a ? $#a : $i+4)]);
  }
  my $median = median(@medians);
  my @smaller = grep {$_ < $median} @a;

  return nth_largest($n, @smaller) if $n < @smaller;

  my @larger = grep {$_ >= $median} @a;
  return nth_largest($n - @smaller, @larger);
}

sub median {
  unshift @_, int(@_/2);
  goto &nth_largest;
}

[download]
In practice it's pretty inefficient, and even proving that it runs in linear time is not entirely trivial!

In reply to Re: Puzzle: The Ham Cheese Sandwich cut. by robin
in thread Puzzle: The Ham Cheese Sandwich cut. by Perl Mouse

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.