#! perl -slw
use strict;
use Benchmark qw[ cmpthese ];

our $N ||= 4000;
our $I ||= -3;

sub qsortr {
	my( $ref, $lo, $hi ) = @_;
	
	my $pivot = $ref->[ ( $lo + $hi ) / 2 ];
	my( $lb, $rb ) = ( $lo, $hi );
	while( 1 ) {
		$lb++ while $ref->[ $lb ] < $pivot; 
		$rb-- while $ref->[ $rb ] > $pivot;
		$lb++ while $lb != $rb and $ref->[ $lb ] == $ref->[ $rb ];
		last if $lb == $rb;
		@{ $ref }[ $lb, $rb ] = @{ $ref }[ $rb, $lb ];
	}
	qsortr( $ref, $lo, $lb ) if $lo < --$lb;
	qsortr( $ref, $rb, $hi ) if $hi > ++$rb;
}

sub qsortv {
	my( $lo, $hi, @data ) = @_;
	
	my $pivot = $data[ ( $lo + $hi ) / 2 ];
	my( $lb, $rb ) = ( $lo, $hi );
	while( 1 ) {
		$lb++ while $data[ $lb ] < $pivot; 
		$rb-- while $data[ $rb ] > $pivot;
		$lb++ while $lb != $rb and $data[ $lb ] == $data[ $rb ];
		last if $lb == $rb;
		@data[ $lb, $rb ] = @data[ $rb, $lb ];
	}
	@data = qsortv( $lo, $lb, @data ) if $lo < --$lb;
	@data = qsortv( $rb, $hi, @data ) if $hi > ++$rb;
	return @data;
}

our @data = map{ int rand( 1000 ) } 1 .. $N;

cmpthese $I, {
    by_value => q[
        my @copy = qsortv( 0, $#data, @data );
        $I == 1 and print "V: @copy";
    ],
    
    xby_ref => q[
        qsortr( \@data, 0, $#data );
        $I == 1 and print "R: @data";
    ],
};

__END__
P:\test>396406 -N=10 -I=1
V: 26 97 100 300 387 391 598 665 853 962
            (warning: too few iterations for a reliable count)

R: 26 97 100 300 387 391 598 665 853 962
            (warning: too few iterations for a reliable count)

                       Rate  xby_ref by_value
xby_ref  1000000000000000/s       --       0%
by_value 1000000000000000/s       0%       --

P:\test>396406 -N=4000 -I=10
            (warning: too few iterations for a reliable count)

            s/iter by_value  xby_ref
by_value      8.79       --    -100%
xby_ref  2.81e-002   31167%       --