This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Possible improvement to std::list::sort


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), then we're still doing better than the worst case
earlier. Of course, if you special-case for 8, we end up using at most
16 comparisons, which is a lot better than the # of comparisons you'd
use to sort 8 elements using merge sort. These tiny hacks could
improve the running time of std::list::sort by a decent fraction.

Regards,
-Dhruv.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]