Home

PLF C++ Library - plf::timsort

Intro

plf::timsort is a small modification of GFX's timsort port (from python/OpenJDK's). Some of the modifications (better compiler and move-semantics support) have been ported back into the original implementation, so mostly what this one does differently is it defines a 'less' function (to avoid including all of <functional>), removes logging and defines a macro which allows other plf containers to detect and use it internally, if it's header it is included in the project prior. Other than that it's all micro-optimizations.

A timsort algorithm can be faster than the quicksort-type algorithms typically used by std::sort implementations but it depends on whether the data is already somewhat-ordered. If the data is mostly sorted already, or the data is in the reverse order that you want it in, it will be faster. In all other cases, you should use std::sort. Benchmark if uncertain. The original project page gives a brief but convincing benchmark of performance in various circumstances.

Implementation

I wanted to optimize GFX's port further, but it's pretty darned efficient as it is. Micro-optimizations aside, the implementation is the same. Read the wikipedia entry for an explanation of timsort's algorithm.

License

plf::timsort is copyright (c) 2011 Fuji, Goro and is under gfx::timsort's permissive MIT license. This means: Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Download

Download here (6kb zip file).
plf::timsort is a simple .h header-only library, to be used with an #include command.

Function Descriptions and Syntax

On the whole, functionality is exactly the same as std::stable_sort. By default the function (timsort()) will use a less-than comparison to sort, but will use the user's comparison function if one is supplied.

// Default sort:
template <typename RandomAccessIterator>
void timsort(RandomAccessIterator const first, RandomAccessIterator const last)

// User-supplied comparison:
template <typename RandomAccessIterator, typename CompareFunction>
inline void timsort(RandomAccessIterator const first, RandomAccessIterator const last, CompareFunction compare)

Examples

#include "timsort.hpp"

std::vector<int> a;

for (int counter = 254; counter != 0; --counter)
{
  a.push_back(counter);
}

plf::timsort(a.begin(), a.end()); // sort in ascending order
plf::timsort(a.begin(), a.end(), std::greater<int>()); // sort in descending order

Version history

Contact: footer
plf:: library and this page Copyright (c) 2017, Matthew Bentley, except timsort implementation.