This is the mail archive of the 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]

Possible improvement to std::list::sort


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:

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

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