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

# Possible improvement to std::list::sort

*From*: Ivo Doko <ivo dot doko at gmail dot com>
*To*: libstdc++ at gcc dot gnu dot org
*Date*: Wed, 08 Oct 2014 01:18:10 +0200
*Subject*: Possible improvement to std::list::sort
*Authentication-results*: sourceware.org; auth=none

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

**Attachment:
**`listsort.h`

*Description:* Text document