Quicksort vs. Shell

[Claudio L.]

(06-21-2014 02:32 PM)Werner Wrote:  In a situation where the bulk of the work is in the comparisons, binary insertion would take constant time, so I don't understand why it would be so much faster for a reversed list?
Werner

Well, the way I implemented it is like this:

You are in the middle of sorting, so you have several elements already sorted, and you are evaluating element An:

A0 ... An-1 , An , ... Unsorted ...

The algorithm takes An, and it compares it with A0 (left of the interval), and if it's less, then it inserts the element at the beginning. If not, it compares with An-1, and if it's bigger, then you leave it there. Only if it's less you start doing the bisection.

So I did the left comparison first, this means on a reversed list, it simply does one comparison, and inserts the element at the beginning of the list. So it's reversing the list with N comparisons.

I could've done the An-1 comparison first, then it would've required 2N comparisons to do the reverse-list case.

That should explain why so fast.
On the other hand, a list that's already sorted would needlessly do 2N comparisons, so for the final implementation I reversed it, now it does the An-1 comparison first.

Claudio