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


in reply to Fastest way to sort a list of integers into 0,1,2,3,-3,-2,-1

I found this a very worthwhile learning experience. Thanks all for the answers and remarks (and haukex for starting it).

I've gathered all versions (as some others also did) and formatted them all alike, all using the *same* *shuffled* input of -50..50

I disabled hdb's solution, as it does not meet the requirements (it sorts the 0 in the middle)

I tested all solutions also against an input list that:

use warnings; use strict; use Benchmark "cmpthese"; use List::Util "shuffle"; use constant DO_CHECK => 0; use if DO_CHECK, "Data::Compare", qw/Compare/; my $bnd = 50; my @in = shuffle (-$bnd .. $bnd); my $exp = [ 0 .. $bnd, -$bnd .. -1 ]; cmpthese (-2, { sortfirst => sub { my @list = @in; @list = sort { $a <=> $b } @list; @list = ((grep { $_ >= 0 } @list), (grep { $_ < 0 } @list)); DO_CHECK and (Compare (\@list, $exp) or die "@list"); }, grepfirst => sub { my @list = @in; my @pos = grep { $_ >= 0 } @list; my @neg = grep { $_ < 0 } @list; @list = ((sort { $a <=> $b } @pos), (sort { $a <=> $b } @neg)) +; DO_CHECK and (Compare (\@list, $exp) or die "@list"); }, packunpck => sub { my @list = map { unpack "l>", $_ } sort map { pack "l>", $_ } +@in; DO_CHECK and (Compare (\@list, $exp) or die "@list"); }, pryrt => sub { sub sgn { $_[0] < 0 ? -1 : 1 } my @list = sort { (sgn ($b) <=> sgn ($a)) || ($a <=> $b) } @in +; DO_CHECK and (Compare (\@list, $exp) or die "@list"); }, choroba => sub { my @list = sort { ((-1, 0, 1)[$a <=> 0] <=> (-1, 0, 1)[$b <=> 0]) || ($a <=> + $b) } @in; DO_CHECK and (Compare (\@list, $exp) or die "@list"); }, choroba0 => sub { # from CB my @list = sort { (($b + .5 <=> 0) <=> ($a + .5 <=> 0)) || ($a <=> $b) } @in; DO_CHECK and (Compare (\@list, $exp) or die "@list"); }, choroba2 => sub { my @list = sort { ((($a <=> 0) & 3) <=> (($b <=> 0) & 3)) || ($a <=> $b) } @in; DO_CHECK and (Compare (\@list, $exp) or die "@list"); }, eily => sub { my @list = sort { ~$b <=> ~$a } @in; DO_CHECK and (Compare (\@list, $exp) or die "@list"); }, vr => sub { # https://www.perlmonks.org/?node_id=1229415 my @list = unpack "i*", pack "I*", sort { $a <=> $b } unpack "I*", pack "i*", @in; DO_CHECK and (Compare (\@list, $exp) or die "@list"); }, Discipulus => sub { # https://www.perlmonks.org/?node_id=1229419 my @list = sort {$a<=>$b} @in; push @list, shift @list until $list[0] >= 0; DO_CHECK and (Compare (\@list, $exp) or die "@list"); }, haukex3 => sub { # based on sortfirst above my @list = sort { $a <=> $b } @in; my $i; for (0 .. $#list) { if ($list[$_] >= 0) { $i = $_; last +; }} # with this module is ~5% faster: # use List::MoreUtils::XS "firstidx"; # my $i = firstidx { $_ >= 0 } @list; @list = (@list[$i .. $#list], @list[0 .. $i-1]); DO_CHECK and (Compare (\@list, $exp) or die "@list"); }, johngg => sub { # https://www.perlmonks.org/?node_id=1229410 my @list = map { unpack q{xl>}, $_ } sort map { my $neg = $_ < 0 ? 1 : 0; pack q{Cl>}, $neg, $_; } @in; DO_CHECK and (Compare (\@list, $exp) or die "@list"); }, Corion => sub { # based on Corion's idea in the CB my @list = sort { $a >= 0 && $b < 0 ? -1 : ($a < 0 && $b >= 0 ? 1 : $a <=> $b) } @in; DO_CHECK and (Compare (\@list, $exp) or die "@list"); }, swl2 => sub { my @list = sort {$a<=>$b} @in; my $i = 0; $i++ while ($list[$i] < 0); push @list, splice @list, 0, $i; DO_CHECK and (Compare (\@list, $exp) or die "@list"); }, tybalt89 => sub { my $high = my @list = sort { $a <=> $b } @in; my $mid = my $low = 0; $list[$mid = $low + $high >> 1] < 0 ? ($low = $mid + 1) : ($high = $mid) while $low < $high; push @list, splice @list, 0, $low; DO_CHECK and (Compare (\@list, $exp) or die "@list"); }, GrepPos => sub { my @list = @in; my $pos = grep { $_ >= 0 } @list; @list[$pos .. $#list, 0 .. $pos - 1] = sort { $a <=> $b } @lis +t; DO_CHECK and (Compare (\@list, $exp) or die "@list"); }, # hdb => sub { # my @list = sort { $a * $b > 0 ? $a <=> $b : $b <=> $a } @in; # DO_CHECK and (Compare (\@list, $exp) or die "@list"); # }, });
Linux 4.20.6-1-default [openSUSE Tumbleweed 20190202] HP ZBook 15G3 C +ore(TM) i7-6820HQ CPU @ 2.70GHz/3480(8 cores) x86_64 15958 Mb Rate pryrt choroba0 choroba choroba2 johngg Corion packu +npck eily grepfirst sortfirst haukex3 GrepPos vr swl2 tybalt89 Disc +ipulus pryrt 2427/s -- -30% -41% -53% -61% -62% +-68% -71% -81% -84% -87% -89% -90% -90% -92% + -93% choroba0 3486/s 44% -- -16% -32% -44% -46% +-53% -59% -73% -77% -82% -84% -86% -86% -88% + -89% choroba 4129/s 70% 18% -- -20% -34% -36% +-45% -51% -68% -73% -78% -82% -83% -84% -86% + -87% choroba2 5132/s 111% 47% 24% -- -18% -20% +-31% -39% -60% -66% -73% -77% -79% -80% -82% + -84% johngg 6280/s 159% 80% 52% 22% -- -3% +-16% -25% -51% -59% -67% -72% -74% -75% -78% + -81% Corion 6455/s 166% 85% 56% 26% 3% -- +-14% -23% -49% -58% -66% -71% -73% -74% -78% + -80% packunpck 7469/s 208% 114% 81% 46% 19% 16% + -- -11% -41% -51% -61% -67% -69% -70% -74% + -77% eily 8413/s 247% 141% 104% 64% 34% 30% + 13% -- -34% -45% -56% -62% -65% -67% -71% + -75% grepfirst 12739/s 425% 265% 209% 148% 103% 97% + 71% 51% -- -16% -33% -43% -47% -49% -56% + -61% sortfirst 15244/s 528% 337% 269% 197% 143% 136% +104% 81% 20% -- -20% -32% -37% -39% -47% + -54% haukex3 19002/s 683% 445% 360% 270% 203% 194% +154% 126% 49% 25% -- -15% -21% -24% -34% + -42% GrepPos 22333/s 820% 541% 441% 335% 256% 246% +199% 165% 75% 46% 18% -- -8% -11% -23% + -32% vr 24206/s 897% 594% 486% 372% 285% 275% +224% 188% 90% 59% 27% 8% -- -4% -16% + -27% swl2 25121/s 935% 621% 508% 390% 300% 289% +236% 199% 97% 65% 32% 12% 4% -- -13% + -24% tybalt89 28845/s 1088% 727% 599% 462% 359% 347% +286% 243% 126% 89% 52% 29% 19% 15% -- + -13% Discipulus 33027/s 1261% 847% 700% 544% 426% 412% +342% 293% 159% 117% 74% 48% 36% 31% 14% + --
Linux 4.4.165-81-default [openSUSE Leap 42.3] HP Z420/1589 Xeon(R) CP +U E5-1650 0 @ 3.20GHz/3533(12 cores) x86_64 15972 Mb Rate pryrt choroba0 choroba Corion choroba2 johngg packu +npck eily grepfirst sortfirst haukex3 GrepPos vr swl2 tybalt89 Disc +ipulus pryrt 6019/s -- -40% -40% -54% -56% -62% +-72% -77% -84% -87% -88% -90% -90% -92% -92% + -93% choroba0 9954/s 65% -- -1% -23% -28% -37% +-53% -61% -74% -79% -81% -83% -84% -86% -87% + -89% choroba 10046/s 67% 1% -- -23% -27% -36% +-53% -61% -73% -79% -81% -83% -83% -86% -87% + -88% Corion 12970/s 115% 30% 29% -- -6% -18% +-39% -50% -66% -73% -75% -78% -79% -82% -84% + -85% choroba2 13770/s 129% 38% 37% 6% -- -13% +-35% -46% -64% -71% -73% -77% -77% -81% -83% + -84% johngg 15761/s 162% 58% 57% 22% 14% -- +-26% -39% -58% -67% -70% -73% -74% -78% -80% + -82% packunpck 21299/s 254% 114% 112% 64% 55% 35% + -- -17% -44% -55% -59% -64% -65% -71% -73% + -75% eily 25713/s 327% 158% 156% 98% 87% 63% + 21% -- -32% -46% -50% -56% -57% -65% -68% + -70% grepfirst 37834/s 529% 280% 277% 192% 175% 140% + 78% 47% -- -20% -27% -36% -37% -48% -52% + -56% sortfirst 47348/s 687% 376% 371% 265% 244% 200% +122% 84% 25% -- -8% -20% -22% -35% -40% + -45% haukex3 51687/s 759% 419% 414% 299% 275% 228% +143% 101% 37% 9% -- -13% -14% -29% -35% + -40% GrepPos 59076/s 882% 494% 488% 355% 329% 275% +177% 130% 56% 25% 14% -- -2% -19% -25% + -32% vr 60424/s 904% 507% 501% 366% 339% 283% +184% 135% 60% 28% 17% 2% -- -17% -24% + -30% swl2 73079/s 1114% 634% 627% 463% 431% 364% +243% 184% 93% 54% 41% 24% 21% -- -8% + -16% tybalt89 79276/s 1217% 696% 689% 511% 476% 403% +272% 208% 110% 67% 53% 34% 31% 8% -- + -9% Discipulus 86809/s 1342% 772% 764% 569% 530% 451% +308% 238% 129% 83% 68% 47% 44% 19% 10% + --

Enjoy, Have FUN! H.Merijn