Sorting is always at least O(n log n). Checking each element is O(n). You don't save anything here by sorting.

Corion: why are you trying to avoid looping? Even if you write some code to solve this problem that doesn't look like it's looping, trust me, it is.

O() only speaks of scalability. It doesn't show that nothing was saved. It wouldn't surprise me to find that Corion's approach is faster, even for long lists. Besides, speed is not the only factor that affects the choice of tools. That said, I don't see the point of sorting here.

for our $n ( map 10**$_, 1, 3, 6 ) {
    print "Benchmarking $n values";
    our @n = map int( rand $n ), 1 .. $n;
    cmpthese -log $n, {
        sort => q[ 
            my $t = $n >> 1; 
            my @m = sort{ $a<=>$b } @n; 
            my $c=0; 
            $c++ while $m[ $c ] <= $t; 
            my $pct= ( @m - $c ) / @m * 100; 
        ],
        grep => q[ 
           my $t = $n >> 1; 
           my $pct = grep({ $_ > $t } @n ) / @n * 100; 
        ],
    };
};;

Benchmarking 10 values
         Rate sort grep
sort 285546/s   -- -62%
grep 751484/s 163%   --

Benchmarking 1000 values
        Rate sort grep
sort  3525/s   -- -71%
grep 12328/s 250%   --

Benchmarking 1000000 values
       Rate sort grep
sort 1.13/s   -- -90%
grep 11.4/s 911%   --
[download]

I know that you don't save much by sorting instead of looping through the whole array, but if you want other ranks/n-tiles than just the one, operating on a sorted list is easier.