ben_sort.pl

sub ben_sort {
	return unless @_ > 1;
	while( 1 ) {
		my $prior = shift;
		my @sublists = ([$prior]);
		my $sublist_ix = 0;
		for my $item (splice @_) {
			my $cmp = $item <=> $prior;
			$sublist_ix += $cmp;
			if( $sublist_ix < 0 ) {
				$sublist_ix = 0;
				unshift @sublists, [];
			} elsif( $sublist_ix > $#sublists ) {
				push @sublists, [];
			}
			push @{ $sublists[$sublist_ix] }, $item;
			$prior = $item;
		}
		my $done = 1;
		for $partial (@sublists) {
			next if @$partial < 2;
			for( 1 .. $#$partial ) {
				next if $partial->[0] == $partial->[$_];
				$done = 0;
				@$partial = ben_sort(@$partial);
				last;
			}
		}
		@_ = map @$_, splice @sublists;
		return @_ if $done;
	}
}