listsort.h

//  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