Possible improvement to std::list::sort

[Dhruv Matani]

>> To improve std::list's sort, (i.e. reduce the # of comparisons),
>> there's a trivial fix that can be done. i.e. Use blocks of 4 elements
>> to merge instead of 1. i.e. Take 4 elements at a time and sort them
>> instead of 1 at a time. If we take 1 element, then in the worst case,
>> sorting 4 elements uses 7 comparisons, and in the best case uses 4
>> comparisons. If we use the min. # of comparisons (5) (can go down to 3
>> in certain cases),

>No, it can't.  If we have 4 elements, any scheme that can go down to 3
>comparisons in certain cases will not manage to get along with at most 5
>comparisons in every other case.  You can't have both.

>Two comparisons can either yield two sorted pairs, or in the best case a
>sorted triple and an untested element.  In the latter case I _have_ to
>compare with the middle of the triple first in order to keep the maximum
>number of comparisons down to 5.

My bad. I think I confused the 2. You're right. I can't have both. If
want the best case 3, then I can't have worst case 5 comparisons.

Isn't that still better than the 7 that we're doing earlier (in the worst case?)

I'm somewhat tempted to write some code to see how much of a
difference this makes.

> In comparison, sorting 8 elements with mergesort has a worst case number
> of comparisons of 17.  I would not call 16 "a lot better" than 17.

I agree.




-- 
   -Dhruv Matani.

"I was a Prisoner of Gravity"
-- Arthur Boorman