Cpp TimSort Versions Save

Hi everyone, this release marks a change of maintainers since Goro Fuji (gfx) couldn't take care of the project anymore. I didn't want to let this project go unmaintained so I offered to take care of it.

The interface of the algorithm remains the same as it was and still works with C++98 and newer C++ standards. However the tooling changed significantly, here is a brief list of overarching changes, which will be described with more detail later:

• The project now has numbered releases following semantic versioning, this is logically version 1.0.0.
• The project layout was changed to conform to the Pitchfork Layout.
• The project now has first-class CMake support.
• The test suite has been revamped.

Bug fixes

The following bugs were fixed:

• Fixed support for move-only types.
• Fixed iterator pointing one element before the beginning of the collection in mergeHi: this sometimes caused issues with std::deque or the MSVC STL debug iterators (issue #30).

Improvements to timsort

The following improvements were made to the code of timsort:

• The algorithm now performs fewer comparisons overall (thanks @mitchblank, #24 #26).
• Some copies/moves to the temporary buffer are now faster (thanks @mitchblank for the ideas in #25).
• mergeLo and mergeHi are faster and don't allocate extra memory anymore when one of the runs contains only one element.
• Move semantics support is properly recognized for more compilers.
• Fixed warning -Winline with GCC.
• Fixed warning C4244 with MSVC.
• Fixed warnings about dead code.

The following changes also affect timsort.hpp:

• The macro GFX_TIMSORT_USE_STD_MOVE can be defined to 0 or 1 to disable or enable move semantics support in gfx::timsort. If this macro is not set, we try to enable move semantics when we detect compiler support.
• The logs are enabled only when the macro GFX_TIMSORT_ENABLE_LOG is defined.
• The assertions are enabled only when the macro GFX_TIMSORT_ENABLE_ASSERT is defined (they previously always fired).
• Everything except the gfx::timsort function was placed in a pseudo-private gfx::detail:: namespace.

Tooling

The tooling was significantly changed prior to this release. One of the main changes was to remove the old project's Makefile and to introduce CMake support instead:

• The new CMakeLists.txt exports the INTERFACE target gfx::timsort.
• The tests can be built with -DBUILD_TESTING=ON and run as CTest tests.
• The benchmarks can be built with -DBUILD_BENCHMARKS=ON.
• The tests can be run through with Valgrind with -DGFX_TIMSORT_USE_VALGRIND=ON.
• The tests can be run with sanitizers with -DGFX_TIMSORT_SANITIZE=<comma-separated-list-of-sanitizers>.
• Both C++98 and C++11 tests are run with the appropriate standard.

The tests were partly rewritten:

• They now use Catch2 instead of Boost.Test.
• They were separated in two files: cxx_98_tests.cpp and cxx_11_tests.cpp which should be compiled with C++98 and C++11 respectively.
• The tests for move-only types where updated to detect more problematic scenarios like self-moves.

The continuous integration was also revised:

• It is now based on CMake & CTest instead of make.
• Tests are now run on Linux (with GCC and Clang), OSX (with AppleClang) and Windows (with MSVC and MinGW-w64).
• Some tests are run with either Valgrind, ASAN or UBSAN.

Other miscellaneous changes:

• The examples don't rely on Boost anymore.
• The benchmark in examples/ was moved to benchmarks/.

This release marks the last commit from the original project before a change of tooling and architecture. After this release, the raw Makefile support will be replaced with CMake support, Boost.Test with Catch2, and the project structure will change a bit.

The algorithm interface itself will remain stable through the new releases: C++ code using gfx::timsort should continue to work.