1.12.0 — Fitness

To my utmost surprise, my life has recently taken a weird turn where I'm doing more fitness-related activities than I thought I would ever do: muscle-strengthening and stretching on a regular basis, and I even started to play badminton again after a 12-year hiatus. My self from three years ago would probably call me a liar while reading those lines. Life can be weird, eh... Anyway, it's still leaving me enough time to work on cpp-sort and to release new versions.

One of the main highlights of this release is the improved support for measures of presortedness: one was added, one was deprecated, and several were improved. As a result, all of the library's measures of presortedness run in O(n log n) or better — save for a deprecated O(n²) that will be removed in the future.

Much effort went into improving the overall library quality: bug fixes, consistency fixes, binary size improvements, better tooling and documentation, etc. One of the biggest items was the switch from GCOV to LCOV as a code coverage engine: it actually reports a correct line coverage while I never managed to get GCOV to show all the lines that were actually covered by the test suite. As a result the library's line coverage is now over 90% and it will now be easier to cover the missing parts.

One of the smaller features that got some library-wide attention is the handling of stable sorting: several bugs were fixed, and a few parts of the library were changed to ensure that stable_t would do a better job at "unwrapping" stable_adapter. These changes caused a few minor breaking changes, which should however not be issues when the library features are used correctly. The documentation was also updated to better explain the logic behind stable_t and stable_adapter (with graphs) and to clarify the expectations around the related type traits.

Deprecations

probe::par

Right invariant metrics and measures of presortedness by V. Estivill-Castro, H. Mannila and D. Wood mentions that:

In fact, Par(X) = Dis(X), for all X.

After checking, it appeared that probe::dis and probe::par indeed both returned the same result for the same input. The authors of Par stopped using Par in their subsequent publications and preferred using Dis instead, so we follow suit and deprecate probe::par accordingly since it is redundant with probe::dis. It will be removed in version 2.0.0.

probe::osc O(n²) fallback

The measure of presortedness probe::osc was improved to run in O(n log n) time and O(n) space instead of O(n²) time and O(1). The old algorithm is still used as a fallback when there isn't enough memory available - to avoid breaking backward compatibility -, but that fallback is deprecated and will be removed in version 2.0.0.

The rationale is that we don't want to keep quadratic algorithms around without a good reason. Measures of presortedness are first and foremost (expensive) diagnostic tools, and as such they aren't expected to run on resource-constrained environments. It makes sense to expect extra memory to be available when suing such tools.

Deprecation warnings can be disabled by defining the preprocessor macro CPPSORT_DISABLE_DEPRECATION_WARNINGS.

New features

New measure of presortedness: probe::block: it implements Block(X) — described by S. Carlsson, C. Levcopoulos and O. Petersson in Sublinear Merging and Natural Mergesort —, slightly modified so that to handle equivalent elements correctly and in a way that makes it a correct measure of presortedness according to the formal definition given by Mannila. Block(X) corresponds to the number of elements in X sequence that aren't followed by the same element in the sorted permutation of X. Its worst case returns |X| - 1 when X is sorted in reverse order.

Bug fixes

• Not all comparisons in probe::osc were performed with the provided comparator, which could lead to compile-time or runtime errors.
• Fixed an issue where merge_insertion_sort and slab_sort produced a memory error (caught by Valgrind and address sanitizer) when called on an empty collection (issue #194).
• stable_adapter<T> did not support construction from T when T was one of the following types (which was not consistent with the other specializations):
  • default_sorter
  • stable_adapter
• stable_adapter<default_sorter>::type now aliases stable_adapter<default_sorter> instead of merge_sorter. This is technically a minor breaking change, but stable_adapter<T>::type is supposed to be constructible from T so the new behavior is correct.
• Since their last rewrite in version 1.9.0, verge_sorter and verge_adapter always used their stable algorithm, even when they weren't wrapped in stable_adapter. That was an accident, and they now use the unstable algorithm by default, as they should have done.

Improvements

• probe::dis now runs in O(n log n) time and O(1) space. When sorting bidirectional iterators, if enough heap memory is available, it uses an O(n) time O(n) space algorithm described by T. Altman and Y. Igarashi in Roughly Sorting: Sequential and Parallel Approach.
• probe::par is now a deprecated alias for probe::dis and thus benefits from the same improvements.
• probe::osc now runs in O(n log n) time and O(n) space. The old algorithm that ran in O(n²) time and O(1) is still used as a fallback when not enough memory is available, but it is deprecated and will be removed in a future breaking version. Thanks a lot to @Control55 from @The-Studio-Discord for coming up with the algorithm.
• stable_t<Sorter> now uses Sorter::type when it exists and Sorter is a stable_adapter specialization.
• stable_adapter<Sorter>::type now does a better unwrapping job when Sorter is itself a stable_adapter specialization.
• sorter_traits now has a partial specialization for stable_adapter where is_always_stable always aliases std::true_type. It was introduced to defensively enforce this contract on user specializations of stable_adapter.
• Some work was done to reduce the size of the binary bloat in various places, with additional small gains in C++17. It is mostly noticeable when the same components are instantiated for different types of collections.
• Reduce recursion in the implementation of quick_merge_sort for forward and bidirectional iterators.

Tooling

Documentation:

• The documentation about measures of presortedness was reworked and improved a bit. A new section describes some measures of presortedness that appear in the literature but don't explicitly appear in the library.
• Improve the documentation for stable_adapter and related feature. Add graphs to visually explain the logic behind them.
• Rewrite parts of the documentation about sorter_traits and related features. Make some usage expectations clearer.
• Fix broken links and Markdown errors.

Test suite:

• WARNING: several changes affect random number generation in the test suite. As a result, errors encountered when running the test suite with specific seeds prior to this release might not be reproduced with new versions of the test suite.
• Bump downloaded Catch2 version to v2.13.7.
• Fix segfaults that occurred when running the memory exhaustion tests with some versions of MinGW-w64.
• Fix some -Winline warnings with GCC and MinGW-w64.
• Fix /W2 conversion warnings with MSVC.
• Test more documented relations between measures of presortedness.
• Add more tests to improve coverage.
• The parts of the test suite that used random numbers have been updated to use less memory at runtime.
• Greatly reduce the number of thread_local pseudo-random engines instantiated by the test suite.

Code coverage:

• Use LCOV instead of gcov in the coverage GitHub Action, which seems to better represent what was really executed, and brings the coverage to more than 90%.
• Bump codecov/codecov-action to v2.
• Update the embedded CMake-codecov scripts, which notably makes code coverage work with MinGW-w64.
• Move codecov.yml to .github/.codecov.yml to reduce the number of files at the root of the project.
• More small tweaks and fixes to the coverage handling in the test suite's CMakeLists.txt and in the GitHub Action.

Miscellaneous:

• GitHub Actions: bump the Ubuntu version from 16.04 to 18.04.
• GitHub Actions: fix the Ubuntu job so that it actually shows the Valgrind logs when a Valgrind jobs fails.
• GitHub Actions: run CTest with --no-tests=error because no tests run by the test suite is always an error.
• Fix includes in benchmarks to work out-of-the-box.
• Simplify the example in the README a bit, and add it to the examples directory.

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.