while now I understand better the matter of sorting, your sentence

> Returning garbage values doesn't not increase the number of comparisons

does not seems to be confirmed by my last example: perl -le "@a = sort{ print qq($a $b); -1 }@ARGV" 1 2 3 4

Infact returning garbage ie: -1 seems to produce always an iteration more in respect of returning 0 or 1

If I understand the mergesort, the above example, should go like:

        1 2 3 4

      [1 2] [3 4]

   [1 3] [3 2] [2 4]
[download]

So only [1 4] is skipped because derived by previous [1 2] [2 4] To notice also that returning -1 as garbage returns a weird sorted list 1 3 2 4 while returning always 1 produce (as I expected) a reversed list: 4 3 2 1

As side effect hacking sort can lead to a new shuffle :)

# naive shuffle

perl -le "print for sort  { int rand(3) - 1 } @ARGV" 1 2 3 4 5

1
3
5
2
4
[download]

L*