Cool! Thanks for that solution, it's exactly what I was going for. :)

Sadly, testing reveals my original hypothesis (that I could obtain stupendous speed improvements by keeping everything as piddles instead of iterating through a "for" loop) to be incorrect. I think the extra computational expense of the second dimension kills my runtime: with $a and $b of size ~3 million, and n=100, it finishes in ~20 seconds vs ~10 seconds for the "for" loop I was trying to improve:

sub test_medians
{
    use strict;
    use warnings;
    use PDL;
    $PDL::BIGPDL = 1;

    my $n = 100;
    my $step = 5;

    my $a = random(3000000)*100;  
    my $b = random(3000000)*1000; 
    $b = $b->qsort;

    my $d = zeroes($n);

    for (my $i=0;$i<$n;$i++)
    {
        $d(($i)) .= $a((($b>($i*$step))*($b<=($i+1)*$step));?)->medove
+r;
    }
    return $d;
}
[download]

Nevertheless, thanks for your help! :)