Repository files navigation

A C++ implementation of TimSort, an O(n log n) stable sorting algorithm, ported from Python's and OpenJDK's.

See also the following links for a detailed description of TimSort:

• http://svn.python.org/projects/python/trunk/Objects/listsort.txt
• http://en.wikipedia.org/wiki/Timsort

This version of the library requires at least C++20. Older versions of the library, available in different branches,offer support for older standards though implement fewer features:

• Branch2.x.y is compatible with C++11, and is slightly more permissive in some reagard due to the lack ofconcepts to constrain its interface (it notaby supports iterators without postfix operator++/--).
• Branch1.x.y is compatible with C++03.Older versions are not actively maintained anymore. If you need extended support for those, please open specificissues for the problems you want solved.

According to the benchmarks,gfx::timsort is slower thanstd::ranges::sort on randomized sequences,but faster on partially-sorted ones. It can be used as a drop-in replacement forstd::ranges::stable_sort,with the difference that it can't fall back to a O(n log² n) algorithm when there isn't enough extra heap memoryavailable.

Merging sorted ranges efficiently is an important part of the TimSort algorithm. This library exposesgfx::timmergein the public API, a drop-in replacement forstd::ranges::inplace_merge with the differencethat it can't fall back to a O(n log n) algorithm when there isn't enough extra heap memory available. According tothe benchmarks,gfx::timmerge is slower thanstd::ranges::inplace_merge on heavily/randomly overlapping subrangesof simple elements, but it is faster for complex elements such asstd::string, and on sparsely overlapping subranges.

The ibrary exposes the following functions in namespacegfx:

// timsorttemplate<    std::random_access_iterator Iterator,    std::sentinel_for<Iterator> Sentinel,typename Compare = std::ranges::less,typename Projection = std::identity>requires std::sortable<Iterator, Compare, Projection>autotimsort(Iterator first, Sentinel last,             Compare compare={}, Projection projection={})    -> Iterator;template<    std::ranges::random_access_range Range,typename Compare = std::ranges::less,typename Projection = std::identity>requires std::sortable<std::ranges::iterator_t<Range>, Compare, Projection>autotimsort(Range &range, Compare compare={}, Projection projection={})    -> std::ranges::borrowed_iterator_t<Range>;// timmergetemplate<    std::random_access_iterator Iterator,    std::sentinel_for<Iterator> Sentinel,typename Compare = std::ranges::less,typename Projection = std::identity>requires std::sortable<Iterator, Compare, Projection>autotimmerge(Iterator first, Iterator middle, Sentinel last,              Compare compare={}, Projection projection={})    -> Iterator;template<    std::ranges::random_access_range Range,typename Compare = std::ranges::less,typename Projection = std::identity>requires std::sortable<std::ranges::iterator_t<Range>, Compare, Projection>autotimmerge(Range &&range, std::ranges::iterator_t<Range> middle,              Compare compare={}, Projection projection={})    -> std::ranges::borrowed_iterator_t<Range>;

Example of using timsort with a defaulted comparison function and a projection function to sort a vector of stringsby length:

#include<string>#include<vector>#include<gfx/timsort.hpp>size_tlen(const std::string& str) {return str.size();}// Sort a vector of strings by lengthstd::vector<std::string> collection = {/* ...*/ };gfx::timsort(collection, {}, &len);

The library is tested with the following compilers:

• Ubuntu: GCC 10, Clang 11
• Windows: MSVC 19.37.32826.1, MinGW-w64 GCC 12
• MacOS: GCC 10, Clang 17

The library can be installed on the system viaCMake (at least 3.14) with the following commands:

cmake -S. -B build -DCMAKE_BUILD_TYPE=Releasecmake --install build

Alternatively the library is also availableConan Center and can be directly installed in your localConan cache with the following command:

conan install --requires=timsort/3.0.1

The following configuration macros allowgfx::timsort andgfx::timmerge to emit diagnostics, which can be helpfulto diagnose issues:

• DefiningGFX_TIMSORT_ENABLE_ASSERT light inserts assertions in key locations in the algorithm to avoid logic errors.
• DefiningGFX_TIMSORT_ENABLE_AUDIT inserts assertions that verify pre- and postconditions. These verifications canslow the algorithm down significantly. Enable the audits only while testing or debugging. Enabling audits automaticallyenables lighter assertions too.
• DefiningGFX_TIMSORT_ENABLE_LOG inserts logs in key locations, which allow to follow more closely the flow of thealgorithm.

cpp-TimSort follows semantic versioning and provides the following macros to retrieve the current major, minorand patch versions:

GFX_TIMSORT_VERSION_MAJORGFX_TIMSORT_VERSION_MINORGFX_TIMSORT_VERSION_PATCH

The tests are written with Catch2 and can be compiled with CMake and run through CTest.

When using the project's mainCMakeLists.txt, the CMake optionBUILD_TESTING isON by default unless theproject is included as a subdirectory. The following CMake options are available to change the way the tests arebuilt with CMake:

• GFX_TIMSORT_USE_VALGRIND: ifON, the tests will be run through Valgrind (OFF by default)
• GFX_TIMSORT_SANITIZE: this variable takes a comma-separated list of sanitizers options to run the tests (empty by default)

Benchmarks are available in thebenchmarks subdirectory, and can be constructed directly by passing the option-DBUILD_BENCHMARKS=ON to CMake during the configuration step.

Example bench_sort output (timing scale: sec.):

c++ -vApple LLVM version 7.0.0 (clang-700.0.72)Target: x86_64-apple-darwin14.5.0Thread model: posixc++ -I. -Wall -Wextra -g  -DNDEBUG -O2 -std=c++11 example/bench.cpp -o .bin/bench./.bin/benchRANDOMIZED SEQUENCE[int]size100000std::sort        0.695253std::stable_sort 0.868916timsort          1.255825[std::string]size100000std::sort        3.438217std::stable_sort 4.122629timsort          5.791845REVERSED SEQUENCE[int]size100000std::sort        0.045461std::stable_sort 0.575431timsort          0.019139[std::string]size100000std::sort        0.586707std::stable_sort 2.715778timsort          0.345099SORTED SEQUENCE[int]size100000std::sort        0.021876std::stable_sort 0.087993timsort          0.008042[std::string]size100000std::sort        0.402458std::stable_sort 2.436326timsort          0.298639

Example bench_merge output (timing scale: milliseconds; omitted detailed results for differentmiddle iterator positions, reformatted to improve readability):

c++ -vUsing built-in specs....Target: x86_64-pc-linux-gnu...gcc version 10.2.0 (GCC)c++ -I ../include -Wall -Wextra -g -DNDEBUG -O2 -std=c++11 bench_merge.cpp -o bench_merge./bench_mergesize100000element type\algorithm:      std::inplace_mergetimmergeRANDOMIZED SEQUENCE[int] approx. average         33.404430         37.047990[std::string] approx. average324.964249        210.297207REVERSED SEQUENCE[int] approx. average         11.441404          4.017482[std::string] approx. average305.649503        114.773898SORTED SEQUENCE[int] approx. average          4.291098          0.105571[std::string] approx. average158.238114          0.273858

Detailed bench_merge results for different middle iterator positions can be found athttps://github.com/timsort/cpp-TimSort/wiki/Benchmark-results