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

[Abigail]

On Thu, Jul 26, 2001 at 10:47:05AM -0400, Clinton A . Pierce wrote:
> 
> If someone can explain *this* to me, I could probably finish a patch
> for in-place sorting in Perl.   But I'm lost as to why (or HOW) @r
> can be "unwound" like this well after the fact.


This approach is never going to work.

You idea is based on the fact that if Perl is going to compare $a and
$b, and they are in the "opposite order", Perl wants $a and $b to be
swapped. 

That is not true. For instance, in the mergesort that is implemented in
5.7.x, in some passes (including, IIRC, the first pass) monotonic
sequences (be them increasing or decreasing) are determined. 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!



Abigail