http://www.perlmonks.org?node_id=998182


in reply to Re: Numeric sorting WITHOUT <=>
in thread Numeric sorting WITHOUT <=>

And here's a Perl 5.16 implementation of quicksort...

use v5.16;
my @sorted = (sub {
    return @_ unless @_ > 1;
    my $pivot = splice(@_, int(@_/2), 1);
    my (@small, @big);
    push @{ $_ < $pivot ? \@small : \@big }, $_ for @_;
    return (__SUB__->(@small), $pivot, __SUB__->(@big))
})->(@unsorted);

[download]

Can be made a little neater using List::MoreUtils...

use v5.16;
use List::MoreUtils 'part';
my @sorted = (sub {
    return @_ unless @_ > 1;
    my $pivot = splice(@_, int(@_/2), 1);
    my ($small, $big) = part { $_ > $pivot } @_;
    return (__SUB__->(@$small), $pivot, __SUB__->(@$big))
})->(@unsorted);

[download]

In older Perls, without __SUB__ you can't recursively call a truly anonymous sub, so you need to have some kind of way of referring to the sub, such as assigning it to a lexical variable...

my @sorted = do { my $SUB; $SUB = sub {
    return @_ unless @_ > 1;
    my $pivot = splice(@_, int(@_/2), 1);
    my (@small, @big);
    push @{ $_ < $pivot ? \@small : \@big }, $_ for @_;
    return ($SUB->(@small), $pivot, $SUB->(@big))
}}->(@array);

[download]
perl -E'sub Monkey::do{say$_,for@_,do{($monkey=[caller(0)]->[3])=~s{::}{ }and$monkey}}"Monkey say"->Monkey::do'

Replies are listed 'Best First'.
Re^3: Numeric sorting WITHOUT <=>
by ikegami (Patriarch) on Oct 10, 2012 at 18:25 UTC
    sort uses mergesort by default, not quicksort. That could be a more appropriate choice?

    Your last snippet has a memory leak.

[reply]
[d/l]

      Mergesort is more complex to implement I think, though not massively so. Perl did once use quicksort, but it was changed in 5.8. The old sorting algorithm can be enabled using:

      use sort '_quicksort';

      [download]

      Memory leak... indeed. Is it too early to be getting sick of pre-5.16 Perls? In practice you'd probably give the sub a name so this wouldn't be an issue.

      perl -E'sub Monkey::do{say$_,for@_,do{($monkey=[caller(0)]->[3])=~s{::}{ }and$monkey}}"Monkey say"->Monkey::do'
[reply]
[d/l]
        Actually, a naïve merge sort is dead simple. Quite possibly the easiest to explain, too. 
        sub mergesort {
   return $_[0] if @_ == 1;

   my $i = int( @_ / 2 );
   my @a = mergesort(@_[0..$i-1]);
   my @b = mergesort(@_[$i..$#_]);

   my @sorted;
   while (@a && @b) {
      if    ($a[0] < $b[0]) { push @sorted, shift(@a);            }
      elsif ($b[0] < $a[0]) { push @sorted, shift(@b);            }
      else                  { push @sorted, shift(@a), shift(@b); }
   }

   return ( @sorted, @a, @b );
}

        [download]

        lol! I got two 5.8.8 question this week. It'll be a while before it's ok to be sick of 5.14.

[reply]
[d/l]

In Section Seekers of Perl Wisdom