This releases comes more than a year after the previous one, and does not have much to offer, which I am blaming on a lack of motivation to work on hobby programming projects for most of a year: all that time was spent learning about various other things, such as brewing beer, learning how to identify plants species more accurately, visiting industrial sites, and reading about miscellaneous things. As you might have guessed from the title, I also underwent a phase of newfound fascination for all things seaweeds, which truly are wonderful creatures in lots of ways.

Fortunately, motivation recently did come back, and after battling CI brownouts and various tooling issues, I could eventually work on actual sorting-related topics again. That work mostly took the shape of improvements around measures of presortedness, with notably a new measure from the literature, a bugfix to another one, a new distribution, and some additions to the documentation, but also more exciting new experiments such as the use of [property-based testing][property-based-testing], as well as a blog post exploring a potential new measure of presortedness.

In the near future, I plan to start releasing new blog posts on The Sparkelling Bedangler either explaining some implementation details of cpp-sort, or exploring sorting-related topics in ways that I can't here.

New features

New measure of presortedness: probe::spear: it implements what is known as the Spearman footrule distance in the realm of statistics, which corresponds to the sum of the distances of all elements of a sequence elements to their sorted position. Its use as a measure of presortedness was proposed Persi Diaconis and Ronald Lewis Graham in Spearman's Footrule as a Measure of Disarray, and appears in the literature under the names $DS$, $D_{S}$ or even just $D$. I decided to rename it $Spear$ for clarity, also to be consistent with the naming of $Ham$, the Hamming distance, which appears under the name $D_{H}$ in some papers.

Technically $Spear$ is not a measure of presortedness according to the original formal definition proposed by Manilla: it does not satisfy the fifth criterion which states that a measure of presortedness $M$ must satisfy the inequality $M(\langle a \rangle X) \le |X| + M(X)$ for any element $a$ of the domain. That said, neither do $Ham$ nor $Osc$ (at least when equivalent elements exist in the sequence), and it never prevented authors from referring to it in the literature about measures of presortedness. If it's any consolation, it satisfies the criterion as revised by Jinseng Chen in Computing and Ranking Measures of Presortedness, which requires that $M(\langle a \rangle X) \le |X| + M(X) + c$, where $c$ is a positive constant.

Bug fixes

Fixed a bug in probe::exc which would cause the algorithm to sometimes return an incorrect value in the presence of equivalent elements (issue #230). For example $Exc(\langle 0, 0, -1 \rangle)$ would return $2$ instead of $1$.

Improvements

Algorithmic & speed improvements:

• Reduce the memory used by indirect_adapter when sorting a random-access range. From a speed point of view, the new version provides small albeit consistent improvements, which can be attributed to a simpler algorithm and one fewer memory allocation - running the benchmark again generally shows slightly different results, with the new version beating the old one on most patterns.
  
• Reduce the memory used by probe::exc, which uses a cycle reordering algorithm similar to that of indirect_adapter.

Other improvements:

• metrics::moves now honours the iterator category of the passed range: if the wrapped sorter behaves differently based on the iterator category of the range to sort, the correct path should now be selected:

  cppsort::metrics::moves<
      cppsort::hybrid_adapter<
          cppsort::insertion_sorter,
          cppsort::heap_sorter
      >
  > sorter;
  std::vector<int> vec = { ... };
  std::list<int> li(vec.begin(), vec.end());
  std::cout << sorter(vec); // Number of moves of heap_sort
  std::cout << sorter(li); // NEW: number of moves of insertion_sort

• The accessor functions of comparison adapters flip, not_fn and projection_compare are now marked [[nodiscard]] when the compiler supports the attribute.
• The experimental libassert support now targets version 2.x.y of the library instead of version 1.x.y.

Tooling

Documentation:

• The page about measures of presortedness was revised a bit:
  • A section was added about $Pos$ being the same as $Ham$.
  • Manilla's criteria were clarified where needed.
  • Some measures of presortedness are now documented as not satisfying some of Manilla's criteria.

The documentation about measures of presortedness will get improved further in a future release.

Benchmarks:

• A new dist::runs distribution accepting a factor parameter in the range [0.0, 1.0] was added. It generates $factor * (|X| - 1)$ evenly distributed step-downs (element followed by a smaller element) in a collection $X$, which is equivalent to $factor * |X|$ runs of similar sizes. This can be used to test whether an algorithm is Runs-adaptive. The following graph displays how regular dist::runs is:

Test suite:

• Introduce RapidCheck to test properties of measures of presortedness, and to generate some basic data distributions on which we test all available sorters.
• Add tests for sorter adapters that are expected to work even when there is no more heap memory available.
• Make "distributions" tests more robust by checking that the sorted collection is not just sorted, but also a permutation of the collection to sort.
• Fix several tests about incorrectly defined relations between measures of presortedness, and add some more from the literature (as well as a conjecture, if that one ever fails we will know for sure that it was incorrect).
• Enable _LIBCPP_REMOVE_TRANSITIVE_INCLUDES with libc++ to catch potential include issues earlier.
• Bump downloaded version of Catch2 to v3.8.1.

CMake:

• cpp-sort can now be installed as a subproject (#225, #226, thanks @Q-Minh).
• When compiling CUDA files with NVCC, the MSVC-specific flags are now correctly forwarded (#227, #228, #229, thanks @Q-Minh).
• The CMake target cpp-sort::cpp-sort does not force the /Zc:preprocessor flag anymore when targeting MSVC, except when libassert support is enabled.
• The vendored version of CMake-codecov was synchronized with upstream.

Continuous integration:

• Upgrade Ubuntu runner image to ubuntu-22.04, bump GCC version to 9, and Clang version to 11,
• Upgrade MacOS runner image to macos-13, bump GCC version to 12.
• Upgrade Windows Server runner image to windows-2022, bump MSVC and MinGW versions accordingly.
• Workaround an issue with sanitizers with Clang 11.
• Workaround issues with lcov and geninfo with recent versions of GCC.
• Merge jobs running ubsan and asan to decrease the overall CI load.

Miscellaneous:

• Add a release_template.md file to the tools 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.

Moreover some compilers emit a few warnings, notably GCC 12, which often spams -Wnonnull and -Warray-bounds when compiling the test suite. I believe that those are false positives, and they seem to disappear with GCC 13. Clang-CL also generates tons of warnings, which I decided to ignore for the time being.