Possible improvement to std::list::sort

[Ivo Doko]

Greetings.

I would like to submit for your consideration an algorithm which, in my 
tests, (mostly) outperforms std::list::sort as currently implemented in 
libstdc++.

For convenience, besides the attachment, the source code is also 
available here: http://pastebin.com/wK5zP2kg

I hope the comments in the code adequately explain how the algorithm 
works. Basically, it is in-place mergesort with an additional pre-merge 
pass which builds sorted regions from pre-existing ascending and 
descending runs. Of course, the sorting is stable.

For lists which are already sorted, the algorithm trivially runs in 
O(n). The same is true for lists which are sorted in reverse and have no 
duplicate values. From my testing, the algorithm performs as well as 
std::list::sort when compiled without optimisation, but with 
optimisation (even with just "-O"), it runs about 30-40% faster than 
std::list::sort on randomly generated lists. (This may imply that the 
code can be additionally optimised, or maybe these are simply 
optimisations beyond a programmer's reach.)

The bad thing, however, is that the worst-case for the algorithm is 
trivially constructible - it is a list of the form
{largest, smallest, 2nd largest, 2nd smallest, ...}.
E.g., for an empty std::list<size_t> lst and length size_t n, this can 
be constructed by the following:

for(size_t i = 0; i < n; ++i)
     lst.emplace_back(i%2 ? i/2 : n - i/2 - 1);

Even in this case, though, the complexity is clearly still O(n log n), 
since the algorithm then operates like regular in-place mergesort, 
having pre-sorted regions of length 2 after the pre-merge pass and using 
n/2+1 additional space for storing the region boundaries before the 
first merge pass. However, in this particular case the algorithm runs 
approximately two times slower than std::list::sort.

Although, it should also be said that I have not analysed the 
implementation of std::list::sort, so I do not know what the worst case 
for it is, hence I could not test how this algorithm compares to 
std::list::sort in that case.

With all this said, I will leave it up to you to decide whether this 
algorithm is an improvement.


--
Ivo Doko
-------------- next part --------------
//  Written in 2014 by Ivo Doko (ivo.doko@gmail.com)

//  To the extent possible under law, the author has dedicated
//  all copyright and related and neighboring rights to this
//  software to the public domain worldwide. This software is
//  distributed without any warranty.

//  See <http://creativecommons.org/publicdomain/zero/1.0/>.

#ifndef _LISTSORT_H
#define _LISTSORT_H 1

#include <list>
#include <algorithm>

template<typename T>
void listsort(std::list<T>& lst)
{
    using lTi = typename std::list<T>::iterator;
    std::list<lTi> boundaries;
    lTi l{lst.begin()},
        r{l};
    //Progressively build sorted regions from
    //ascending and descending runs until the
    //end of the list is reached.
    while(l != lst.end())
    {
        lTi li{l};
        ++li;
        while(li != lst.end())
        {
            //li is always one place ahead of r,
            //so in this case just move r one
            //place forward.
            if(*li >= *r) { ++r; ++li; }
            else
                //Place values smaller than *l before
                //l and change l to point to the new
                //minimum.
                if(*li < *l)
                {
                    lTi moved{li++};
                    lst.splice(l, lst, moved);
                    --l;
                }
                //If the value can't be placed neither
                //before l nor after r, stop building
                //the current region.
                else break;
        }
        //Add l to the list of region boundaries and
        //continue with building the following region.
        boundaries.emplace_back(l);
        l = ++r;
    }
    //Add the end of the list as the final region boundary.
    boundaries.emplace_back(lst.end());
    //Merge pairs of adjacent regions until only two
    //boundaries remain - lst.begin() and lst.end().
    using lBi = typename std::list<lTi>::iterator;
    while(boundaries.size() > 2)
    {
        lBi ri{boundaries.begin()};
        while(*ri != lst.end())
        {
            lBi ri_a{ri++};
            if(*ri == lst.end()) break;
            lBi ri_b{ri++};
            //Merge regions [*ri_a, *ri_b) and [*ri_b, *ri)
            //and then remove ri_b from the list of region
            //boundaries.
            std::inplace_merge(*ri_a, *ri_b, *ri);
            boundaries.erase(ri_b);
        }
    }
}

#endif // _LISTSORT_H