Re^2: Fastest way to sort a list of integers into 0,1,2,3,-3,-2,-1

[Eily]

You missed one step in the last two. Instead of:

my @list = @input;
@list = EXPR @list;

You wrote:

my @list = EXPR @input;

I don't know exactly how well perl optimizes, but there's a chance you're skipping one copy of the values, and one overwrite of the content of @list. On my computer your Discipulus2 rewritten to have the same format as the other tests is slightly slower than using first_index (like haukex did in the comments of his code, rather than the code itself?) with push and splice. Now the "NoOverwrite" below is just your Discipulus2 where the absence of overwrite of @list is made explicit, and I have not been able to beat that one. Edit: nope, that code was wrong. Fixed, and first_index wins:

use warnings;
use strict;
use Benchmark 'cmpthese';
use constant DO_CHECK => 0;
use if DO_CHECK, 'Data::Compare', qw/Compare/;
use List::MoreUtils qw( first_index );

my @input = (-57..50,52,0);
my @output = (0,0..50,52,-57..-1);
use List::Util 'shuffle';
srand 123;
@input = shuffle @input;

cmpthese(DO_CHECK ? 1 : -2, {
  Eily => sub { # https://www.perlmonks.org/?node_id=1229411
    my @list = @input;
    @list = sort { ~$b <=> ~$a } @list;
    Compare(\@list,\@output) or die "@list" if DO_CHECK;
  },
  vr => sub { # https://www.perlmonks.org/?node_id=1229415
    my @list = @input;
    @list = unpack 'i*', pack 'I*', sort { $a <=> $b }
      unpack 'I*', pack 'i*', @list;
    Compare(\@list,\@output) or die "@list" if DO_CHECK;
  },
  Discipulus => sub{ # https://www.perlmonks.org/?node_id=1229419
    my @list = @input;
    my @neg = sort {$a<=>$b} grep { $_ < 0 } @list;
    my @pos = sort {$a<=>$b} grep { $_ >= 0} @list;
    @list = (@pos,@neg);
    Compare(\@list,\@output) or die "@list" if DO_CHECK;
  },
  Discipulus2 => sub{ # https://www.perlmonks.org/?node_id=1229419
    my @list = @input;
    @list = sort {$a<=>$b} @list;
    push @list, shift @list until $list[0] >= 0;
    Compare(\@list,\@output) or die "@list" if DO_CHECK;
  },
  NoOverwrite => sub{ # Actually Discipulus2
    my @list = @input;
    my @sorted = sort {$a<=>$b} @list; # Don't overwrite
    push @sorted, shift @sorted until $sorted[0] >= 0;
    Compare(\@list,\@output) or die "@list" if DO_CHECK;
  },
  Splice_FirstIdx => sub{ # Haukexish
    my @list = @input;
    @list = sort { $a <=> $b } @list;
    my $nb_neg = first_index { $_ >= 0 } @list;
    push @list, splice @list, 0, $nb_neg;
    Compare(\@list,\@output) or die "@list" if DO_CHECK;
  },
});

__END__
                   Rate Eily Discipulus   vr NoOverwrite Discipulus2 S
+plice_FirstIdx
Eily            19851/s   --       -55% -65%        -68%        -72%  
+          -75%
Discipulus      43848/s 121%         -- -23%        -28%        -37%  
+          -44%
vr              56978/s 187%        30%   --         -7%        -18%  
+          -28%
NoOverwrite     61148/s 208%        39%   7%          --        -12%  
+          -22%
Discipulus2     69804/s 252%        59%  23%         14%          --  
+          -11%
Splice_FirstIdx 78838/s 297%        80%  38%         29%         13%  
+            --