while now I understand better the matter of sorting, your sentence

> Returning garbage values doesn't not increase the number of comparisons

does not seems to be confirmed by my last example: perl -le "@a = sort{ print qq($a $b); -1 }@ARGV" 1 2 3 4

Infact returning garbage ie: -1 seems to produce always an iteration more in respect of returning 0 or 1

If I understand the mergesort, the above example, should go like:

        1 2 3 4

      [1 2] [3 4]

   [1 3] [3 2] [2 4]
[download]

So only [1 4] is skipped because derived by previous [1 2] [2 4] To notice also that returning -1 as garbage returns a weird sorted list 1 3 2 4 while returning always 1 produce (as I expected) a reversed list: 4 3 2 1

As side effect hacking sort can lead to a new shuffle :)

# naive shuffle

perl -le "print for sort  { int rand(3) - 1 } @ARGV" 1 2 3 4 5

1
3
5
2
4
[download]

L*

I did mention there are optimizations at play over a pure merge sort.

In fact, my testing shows that passing n sorted items, it only performs n comparisons. This is clearly not the behaviour of a pure merge sort.

But I was indeed wrong about the amount being constant.

• Merging 1,2,3 with 4,5,6 requires three comparisons.
• Merging 1,7,8 with 4,5,6 requires four comparisons.

In fact, my testing shows that passing n sorted items, it only performs n comparisons.

Except kind of anomaly in ~ 5..17 range:

use strict;
use warnings;
use Chart::Gnuplot;

my @x = ( 2 .. 50 );
my @y = map { 
    my $n = 0;
    1 for sort { ++ $n; $a <=> $b } 1 .. $_;
    $n
} @x;

my $chart = Chart::Gnuplot-> new( 
    gnuplot  => 'gnuplot.exe',
    terminal => 'dumb size 60, 30',
    xrange   => [ 0, 50 ],
    yrange   => [ 0, 50 ],
    title    => 'Number of comparisons vs pre-sorted array length',
);
my $dataset = Chart::Gnuplot::DataSet->new(
    xdata => \@x,
    ydata => \@y,
    style => 'impulses',
);

__END__

      Number of comparisons vs pre-sorted array length

  50 +--------------------------------------------------+
     |         +         +          +         +       **|
     |                                              ****|
     |                                            ******|
     |                                          ********|
  40 |-+              *                       **********|
     |                *                     ************|
     |                *                   **************|
     |                *                 ****************|
     |              ***               ******************|
  30 |-+           ****             ********************|
     |            *****           **********************|
     |           ******        *************************|
     |          *******     ** *************************|
  20 |-+        *******   **** *************************|
     |        ********* ****** *************************|
     |        **************** *************************|
     |        **************** *************************|
     |       ***************** *************************|
  10 |-+    ****************** *************************|
     |    ******************** *************************|
     |    ******************** *************************|
     |   ********************* *************************|
     |  ********************** *************************|
   0 +--------------------------------------------------+
     0         10        20         30        40        50
[download]

Just for fun..

obfuscated shuffle can be sort {--$|} but, as expected, List::Util shuffle is a bit more performant

use strict;
use warnings;
use Benchmark qw(cmpthese);
use List::Util qw(shuffle);

my $count = 10000;
my @numbers = 0..10000;

cmpthese($count, {
    'List::Util::shuffle' => sub { my @shuffled = shuffle @numbers },
    'Discipulus::shuffle' => sub { my @shuffled = sort { int rand(3) -
+ 1 } @numbers },
    'Discipulus::--$|fle' => sub { my @shuffled = sort { --$| } @numbe
+rs },
});

__END__
                      Rate Discipulus::--$|fle Discipulus::shuffle Lis
+t::Util::shuffle
Discipulus::--$|fle  164/s                  --                -52%    
+            -95%
Discipulus::shuffle  342/s                108%                  --    
+            -89%
List::Util::shuffle 3107/s               1793%                809%    
+              --
[download]

L*

There are no rules, there are no thumbs..
Reinvent the wheel, then learn The Wheel; may be one day you reinvent one of THE WHEELS.

that's the price you pay when you want your pipes piping hot