basically it's like a logical puzzle you have to solve with asking a *minimum* number of questions (like "is 1 less than 2?") and (ideally) employing heuristics and the identities that hv mentions. In fact Perl's sort does a good job: perl -le 'my $iters;@a=sort{ $iters++; $a<=>$b }map { int rand 50000 }(1..500); print $iters' 3852 whereas an exhaustive sort would ask 500*499/2=124750 questions. So Do What I Mean and Don't @&*%$ Ask Me More Questions Than Necessary hehe

Here is another way to irritate Perl's sort: perl -le 'my$iters;@a=sort{ $iters++;print qq($a $b); [-1,0,1]->[int rand 3] }map { int rand 50000 }(1..500); print $iters'

Edit: see Acme::ICan for another kind of sort