#! perl -slw
use strict;
use List::Util qw[ shuffle ];

use Inline C => 'DATA';

$^W = 0;
 
my $max = 120;
my @values = 1 .. $max;
my @values_mixed = shuffle(@values);
my @top = topNbs(20, sub { $a <=> $b }, \@values_mixed);
print "@top";
 
__END__
__C__

int callComp( SV* cmp, SV* a, SV* b ) {
	dSP;
	int rv;
	ENTER; 
	SAVETMPS; 

	GvSV(gv_fetchpv("a", TRUE, SVt_PV)) = a;
	GvSV(gv_fetchpv("b", TRUE, SVt_PV)) = b;
	
	PUSHMARK(SP);

	if( call_sv( cmp, G_SCALAR|G_NOARGS ) != 1 )
		croak( "Bad comparator" );
	SPAGAIN;

	rv = POPi;

	PUTBACK; // << Was missing and is required!
	FREETMPS;LEAVE;
	return rv;
}
 
void topNbs( int n, SV *cmp, AV*data) {
    SV* *topN;
    int len = av_len( data );
    int i, j, k;
    int left, right;
    Inline_Stack_Vars;
    Newz( 1, topN, n + 1, SV* );
 
    for (i = 0; i < n+1; i++) {
       topN[i] = newSViv( 0 );
    }
 
    for( i = 0; i <= len; i++ ) {
        SV *val = *av_fetch( data, i, 0 );
        if (callComp(cmp, val, topN[ n - 1]) < 0) continue;
 
        left = 0;
        right = n - 1;
        while (left < right) {
           int middle = (left + right) >> 1;
           if (callComp(cmp, val, topN[ middle ]) <= 0) {
              left = middle + 1;
           } else {
              right = middle;
           }
        }
	for( k = n; k > left; k-- ) topN[ k ] = topN[ k-1 ];
	topN[ left ] = val;
    }
 
    Inline_Stack_Reset;
    for( i = 0; i < n; i++ )
        Inline_Stack_Push( sv_2mortal( newSVsv( topN[ i ] ) ) );
    Safefree( topN );
    Inline_Stack_Done;
}