Possible improvement to std::list::sort

[Ivo Doko]

On 2014-10-08 05:48, David Kastrup wrote:
> That being said, I am not a fan of special-casing pre-sorted cases in
> generic routines.  If the case occurs often enough in practice, the
> application should invest the extra effort of doing the check itself.
> Mergesort "special-cases" presorted material already by requiring about
> half the number of comparisons than usual.  Of course, that's still
> O(n lg n) rather than O(n), but it will also have benefits for partially
> sorted lists.

Oh, just wanted to point out - I have not actually "special-cased" the 
pre-sorted cases.

If you take a look at the code, you will see that the O(n) (actually 
just a single pass through the list - so, n) complexity for sorted and 
backwards-sorted lists is a simple consequence of the pre-merge pass 
which builds sorted regions out of pre-existing runs. In case of a 
sorted list (or a backward-sorted list with no duplicate values 
(required in order to keep the sort stable)), this pass will result in a 
single region, i.e. only two region boundaries - the .begin() and .end() 
of the list. Since the following loop (the merge-sort part of the 
algorithm) loops while there are more than two region boundaries, the 
loop body won't even be entered.


--
Ivo Doko