1.10.0 — Dreams

Here comes a new release after merely two months, making it the minor version of the library with the shortest development cycle so far. I haven't done anything super interesting recently so that release name is dedicated to all the dreams I've written down since the beginning of the pandemic, mostly adventures, improbably situations and lots of fun — it's nice being able to live adventures in my dreams when every day life is slow. Speaking of fun: it was pretty much the leading force behind this release, which was reified as one new measure of presortedness and three new sorters, mostly implemented after research papers from the 80s and 90s.

One of the most important (but not fun) changes is that cpp-sort now works with MSVC 2019 (only with /permissive-): the compiler front-end evolved sufficiently to compile most of the library, so I decided to change the library where needed to fully support it — which also allowed to fix small bugs in several parts of the library, improving its overall quality. The only big feature that still doesn't work is the ability to convert a sorter to a variety of function pointers (issue #185).

New features

New sorters: one of the goals of this release was to be fun, and what's more fun than implementing unknown algorithms from old research papers without having to care about them being the fastest in the land? This release adds several new sorting algorithms, mostly found in the literature about adaptive sorting from the 80s and 90s. On average those new algorithms are adaptive, but slow and impractical for most real world use. However their inclusion in the library means that they now have an open-source implementation, which is always something valuable.

• cartesian_tree_sorter: it implements a Cartesian tree sort, an Osc-adaptive comparison sort introduced by C. Levcopoulos and O. Petersson in Heapsort - Adapted for Presorted Files under the name maxtree-sort. The algorithm uses a Cartesian tree and a heap to sort a collection.
• mel_sorter: it implements melsort, an Enc-adaptive comparison sort described by S. Skiena in Encroaching lists as a measure of presortedness. It works by creating encroaching lists with the elements of the collection to sort then merging them. When used together with container_aware_adapter, mel_sorter provides specific algorithms for std::list and std::forward_list than run in O(sqrt n) extra memory instead of O(n).
• slab_sorter: it implements slabsort, an SMS-adaptive comparison sort described by C. Levcopoulos and O. Petersson in Sorting Shuffled Monotone Sequences. The algorithm builds upon the adaptiveness of melsort to take advantage of even more existing presortedness in sequences to sort.

Measures of presortedness (MOPs): the literature about adaptive sorting is also about MOPs, so those were given some love for the first time in a while:

• New MOP probe::sus which implements SUS(X) as described by Levcopoulos and Petersson in Sorting Shuffled Monotone Sequences. It computes the minimum number of non-decreasing subsequences (of possibly not adjacent elements) into which X can be partitioned. It happens to correspond to the size of the longest decreasing subsequence of X. Its worst case returns n - 1 when X is sorted in reverse order.
• MOPs now all have a static max_for_size function which takes a size and returns the maximum value that the MOP can return for the given size. This helps to give a better scale for how much presortedness represents the value returned by a specific MOP.

More constexpr: this release also brings very basic constexpr support to some of the library's building blocks: sorter_facade, iter_move and iter_swap. None of the library's sorters or sorter adapters have been updated to work in a constexpr context (this would require C++17/C++20 library features, or reinventing the wheel again), but these changes mean that it is possible for a user to write a constexpr-friendly sorter implementation, wrap it with sorter_facade, and get a - mostly - constexpr sorter ("mostly" because the ranges overload require C++17 features to work in a constexpr context). More comprehensive constexpr support is planned for a future 2.0.0 release (see issue #58).

Bug fixes

• Fix out-of-bounds iterator issue in merge_insertion_sorter (issue #182).
• Fix out-of-bounds iterator issues in grail_sort (issue #183).
• Fix incorrect destruction of some elements in merge_insertion_sorter (issue #184).
• Fix integer overflows in the branchless partitioning algorithm of pdq_sort (see upstream issue orlp/pdqsort#13), potentialy affecting all of the library components that rely on it.
• Fix a rather obscure issue potentially affecting projection_compare, stable_adapter and std_sorter, as well as container_aware_adapter<merge_sorter> when used for std::list or std::forward_list (issue #139, huge thanks to @sehe for debugging that one).
• Fix the check for std::identity with libstdc++.
• The check for std::identity now works on non-Clang non-GCC compilers.
• Calls to std::min and std::max are now consistently wrapped in parenthesis to avoid clashes with popular min() and max() macros.

Improvements

• The conversion from a sorter to a function pointer is now unconditionally constexpr (it used to only be constexpr in C++17 mode and later).
• Change grail_sort to use difference_type instead of int wherever it matters in its implementation. It solves some conversion warnings, and might even solve potential overflow issues with big collections.
• Silence several conversion warnings.
• probe::enc now performs up to 40% fewer comparisons.
• Reduce the number of allocations performed by merge_insertion_sorter. This doesn't affect its speed nor its memory complexity.

Tooling

Benchmarks:

• The distributions are now constructed with a long long int instead of a size_t.
• Change the default patterns in the patterns benchmark.

Documentation:

• Complete the introduction about MOPs, add a graph showing the partial ordering for MOPs.
• Remove mentions of Bintray.

Test suite:

• Test that all sorters handle projections returning an rvalue.
• Add minimal to check that sorters behave correctly when a move operation throws.
• Test that all MOPs return 0 when given a collection of equivalent values.
• Test more relations between MOPs described in the literature.
• Remove alternating_16_values tests, they never gave results significantly different from shuffled_16_values.
• The distributions are now constructed with a long long int instead of a size_t.
• The whole test suite was successfully compiled and executed with -no-rtti.

Miscellaneous:

• Add MSVC 2019 builds to the continuous integration.
• The minimal supported Conan version is now 1.32.0.
• The configuration checks in conanfile.py were moved from configure() to validate().
• No more @morwenn/stable packages on Bintray: JFrog is sunsetting Bintray. Only the Conan Center packages will be updated from now on.
• Tweak tools/test_failing_sorter.cpp to make it more useful.

Known bugs

I didn't manage to fix every bug I could find since the previous release, so you might want to check the list of known bugs.