P:\test>282315 -N=100 -MAX=500000 -TRIALS=1
499984 499984 499984 499984 499984 499984 499984 499984 499984 499984 499984
499984 499984 499984 499984 499984 499984 499984 499984 499984 499984 499984
     1 trial  of insertion sort (8.002s total)

     1 trial  of standard sort & slice (26.198s total)

##</code><code>##

P:\test>282315 -N=100 -MAX=1000000 -TRIALS=1
999969 999969 999969 999969 999969 999969 999969 999969 999969 999969 999969 9
999969 999969 999969 999969 999969 999969 999969 999969 999969 999969 999969 9
     1 trial  of insertion sort (15.733s total)

     1 trial  of standard sort & slice (90.730s total)

##</code><code>##

#! perl -slw
use strict;
use Benchmark::Timer;

my $T = Benchmark::Timer->new;

use vars qw[ $N $MAX $TRIALS ];
$N ||= 10; $MAX ||= 100; $TRIALS ||= 10;

srand(1);
my @unsorted = map{ int rand $MAX } 1 .. $MAX;

my @topN1;
for( 1 .. $TRIALS ) {
	@topN1 = ();
	$T->start( 'insertion sort' );
	iSortN( \@topN1, $N, \@unsorted );
	$T->stop( 'insertion sort' );
}
print "@{[ reverse @topN1 ]}";

my @topN2;
for( 1 .. $TRIALS ) {
	$T->start( 'standard sort & slice' );
	@topN2 = ( sort{ $b <=> $a } @unsorted )[ 0 .. ($N-1) ];
	$T->stop( 'standard sort & slice' );
}
print "@{[ @topN2 ]}";

$T->report;

exit;

use constant { AREF=>0, LISTSIZE=>1, INPUT=>2 };

sub iSortN {
# AREF = Array ref to hold the list.
# LISTSIZE = then number of elements to retain.
# Either a single value or an array ref to a batch of values

# One peculiarity of the implementation is that the list comes back in reverse order. 
# Fixing this is an exercise for the user:)

	my $input = ref $_[INPUT] ne 'ARRAY' ? [ $_[INPUT] ] : $_[INPUT];

	push( @{ $_[AREF] }, 0 ) unless @{ $_[AREF] };

	for ( @{ $input } ) {
		if( $_ <= $_[AREF]->[ 0 ] ) {
			unshift @{ $_[AREF] }, $_;
		}
		elsif( $_ >= $_[AREF]->[ -1 ] ) {
			push @{ $_[AREF] }, $_;
		}
		else {
			splice @{ $_[AREF] }, bsearch( $_[AREF], $_ ), 0, $_;
		}
		shift @{ $_[AREF] } if @{ $_[AREF] } > $_[LISTSIZE];
	}
}

sub bsearch {
	my( $aref, $value ) = @_;
	my( $lo, $hi, $mid ) = ( -1, $#{ $aref }, 0 );

	while( $lo <= $hi ) {
		$mid = int( ($lo + $hi) / 2 );
		if(   $value > $aref->[ $mid ] ) {
			$lo = ++$mid;
		}
		elsif( $value < $aref->[ $mid ] ) {
			$hi = --$mid;
		}
		else {
			return $mid
		}
	}
	return $aref->[ $mid ] > $value ? $mid : $mid+1;
}



__END__
P:\test>282315 -N=10 -MAX=10000
9999 9998 9997 9997 9996 9996 9994 9992 9990 9990
9999 9998 9997 9997 9996 9996 9994 9992 9990 9990
    10 trials of insertion sort (1.612s total), 161.232ms/trial

    10 trials of standard sort & slice (1.031s total), 103.148ms/trial


P:\test>282315 -N=10 -MAX=100000
99996 99996 99996 99996 99996 99996 99993 99993 99993 99990
99996 99996 99996 99996 99996 99996 99993 99993 99993 99990
    10 trials of insertion sort (16.424s total), 1.642s/trial

    10 trials of standard sort & slice (17.645s total), 1.765s/trial


P:\test>282315 -N=10 -MAX=200000
199993 199993 199993 199993 199993 199993 199993 199993 199993 199993
199993 199993 199993 199993 199993 199993 199993 199993 199993 199993
    10 trials of insertion sort (31.996s total), 3.200s/trial

    10 trials of standard sort & slice (37.694s total), 3.769s/trial


P:\test>282315 -N=10 -MAX=300000
299990 299990 299990 299990 299990 299990 299990 299990 299990 299990
299990 299990 299990 299990 299990 299990 299990 299990 299990 299990
    10 trials of insertion sort (47.869s total), 4.787s/trial

    10 trials of standard sort & slice (62.895s total), 6.289s/trial


P:\test>282315 -N=10 -MAX=500000

P:\test>282315 -N=10 -MAX=500000 -TRIALS=1
499984 499984 499984 499984 499984 499984 499984 499984 499984 499984
499984 499984 499984 499984 499984 499984 499984 499984 499984 499984
     1 trial  of insertion sort (8.833s total)

     1 trial  of standard sort & slice (30.524s total)


P:\test>282315 -N=100 -MAX=500000 -TRIALS=1
499984 499984 499984 499984 499984 499984 499984 499984 499984 499984 499984
499984 499984 499984 499984 499984 499984 499984 499984 499984 499984 499984
     1 trial  of insertion sort (8.002s total)

     1 trial  of standard sort & slice (26.198s total)


P:\test>282315 -N=100 -MAX=1000000 -TRIALS=1
999969 999969 999969 999969 999969 999969 999969 999969 999969 999969 999969 9
999969 999969 999969 999969 999969 999969 999969 999969 999969 999969 999969 9
     1 trial  of insertion sort (15.733s total)

     1 trial  of standard sort & slice (90.730s total)