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; }