Re: Sorting in-place (SOLVED? No, further mysteries!)

[Bart Lateur]

On Thu, 26 Jul 2001 18:58:21 -0400, Bernie Cosell wrote:

>> ...If you 
>> would then swap pairs, Perl will think the entire array is already
>> monotonic - and you will have a sort that runs in linear time!
>
>And what's wrong with that?

The fact that it would be a lie? A distant cousin of the perpetuum
mobile, perhaps?

I'm not really sure if you are serious, or just jesting.

Perl's sort is based upon the idea that $a and $b are fixed, thereby
allowing skipping some unnecessary comparisons, because the outcome can
already be known. For example, when comparing "A", "B" and "C", it's
enough to compare "A" with "B", and "B" with "C", to know the result of
comparing "A" with "C". Thus, you can skip that comparison.

When you start swapping items, you invalidate this supposition. The
items become moving targets. It's just like trying to count ants in a
whirling nest.

I'm sure somebody can come up with a counter example. Just not me, not
at this time of the night.

-- 
        Bart.