Re^3: sort of misunderstanding of sort

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.

Comment on Re^3: sort of misunderstanding of sort

Replies are listed 'Best First'.

Re^4: sort of misunderstanding of sort
by Anonymous Monk on Mar 23, 2023 at 00:13 UTC

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]

[reply]
[d/l]


Welcome to the Monastery
	PerlMonks