G'day builat,

To determine whether some piece of code is faster than another, use the Benchmark module. (In case you didn't know, this is part of the standard Perl distribution: you'll already have it installed.)

Specifically for sorting routines, take a look at both the sort function and the sort pragma. Note the various caveats and warnings, particularly with respect to usage with different Perl versions and deprecation of '_SUBPRAGMA'.

I ran a few tests with the code you've presented here. Your sortQ() routine is roughly an order of magnitude slower than the standard "sort { $a <=> $b } ..." (ascending, numerical) code.

I also found that with (what I'd consider) small arrays of just a few hundred elements, and a relatively high number of duplicates, I got screenfuls of "Deep recursion on subroutine "main::sortQ" ..." messages.

So, test your code with various array sizes, numbers of duplicates (which equates to the range of random numbers) and any other variable factors. Only when you have code that passes your tests should you consider benchmarking: it doesn't matter how fast broken code completes!

Every recursion can be rewritten as a loop, avoiding calls and parameter passing can result into considerable speed gain.

Thank you for your response.
Indeed, as I wrote above all idea is to learn how to write better code.
Certainly in the production decisions sort will be used.

With just a few syntax changes (no change to the logic) I can shave off about 8% of the run time...

sub sortQ2
{
    my ($s, $e, $dst) = @_;
    my $m = $s - 1;
    
    ($dst->[$_] < $dst->[$e]) && (
        ++$m,
        ($dst->[$m], $dst->[$_]) = ($dst->[$_], $dst->[$m]),
    ) for ($s .. $e-1);
    
    ++$m;
    
    ($dst->[$m], $dst->[$e]) = ($dst->[$e], $dst->[$m]);
    
    sortQ2($s, $m-1, $dst) if ($s < $m - 1);
    sortQ2($m+1, $e, $dst) if ($m + 1 < $e);
}
[download]

How does this speed things up? Each pair of { ... } introduces a lexical scope; scopes have a small runtime overhead. I've removed all of them except for the one surrounding the entire function.

You can get a few percent extra using Data::Alias which allows you to avoid some arrayref dereferencing operations:

use Data::Alias;

sub sortQ2
{
    my ($s, $e, $dst) = @_;
    alias my @dst = @$dst;
    my $m = $s - 1;
    
    ($dst[$_] < $dst[$e]) && (
        ++$m,
        ($dst[$m], $dst[$_]) = ($dst[$_], $dst[$m]),
    ) for ($s .. $e-1);
    
    ++$m;
    
    ($dst[$m], $dst[$e]) = ($dst[$e], $dst[$m]);
    
    ($s < $m - 1) && sortQ2($s, $m-1, $dst);
    ($m + 1 < $e) && sortQ2($m+1, $e, $dst);
}
[download]

Overall, this is about 12% faster than the original.

See you and raise you to 34% :)

sub sortQ3{
    local our @dst;
    ( my( $s, $e ), *dst ) = @_;
    my $t;
    my $m = $s-1;
    $dst[ $_ ] < $dst[ $e ]
        and $t = $dst[++$m], $dst[$m] = $dst[$_], $dst[$_] = $t
        for $s .. $e;

    $t = $dst[++$m], $dst[$m] = $dst[$e], $dst[$e] = $t;

    sortQ3( $s, $m-1, \@dst ) if $s  < $m-1;
    sortQ3( $m+1, $e, \@dst ) if $m+1< $e;
}
[download]

---

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.
.

Hmm... I'm surprised that introducing that temporary variable for swaps makes such a difference, but it does appear to. Do you have any explanation? Is it because it's saving a couple of array indexing operations, or is it just that ($x,$y)=($y,$x) is implemented suboptimally by Perl?

use Moops; class Cow :rw { has name => (default => 'Ermintrude') }; say Cow->new->name

my (@out,$ref) = undef;
[download]

My guess as to the intent of this statement from the OPed code is that it was to be some kind of self-documentation of the creation of two lexical variables: an empty array and an undefined scalar. It does not do what I think you think it does.

In fact, it is equvalent to the
    my (@out, $ref) = (undef);
statement, which uses the list  (undef) to initialize the newly-created lexicals. However, due to list flattening, the  @out array 'consumes' all the elements of the initialization list, thus producing a non-empty array with a single element: undef. In view of the  push @out, ...; statement in the subsequent for-loop, it seems unlikely this behavior was intended. (But the  $ref scalar remains undefined after all this!)

>perl -wMstrict -MData::Dump -le
"my (@out,$ref) = undef;
 dd \@out;
"
[undef]
[download]

Thank you all once again.
My piggy bank updated with new unknown to me techniques.