Unexpectedly long sort times.

[Søren Kyale]

Cathy,

I think you asked about a quick sort that was showing On^2 time on random sorts.

It might be doing insertion sort style swaps (moving all the between elements over one). This requires n*n/2 swaps in the best case on the first run. So the first run has an n^2 component that will cause On^2 behavior even if all of the comparisons in were done in zero time.

The logn comes because each time the list is split in half n is divided by two. This means the number of operations required is the number for the first pass times (one + the log of n). One + log n is the number of passes requires a roughly constant fraction of the operations on the previous pass.

I also think I finally figured out how to make a reasonably fast (only 5 times slower than sorted) stable quick sort that sorts in place.