cpp-sort v2.2.0

Sorting algorithms & related tools for C++

Release notes

[![DOI](https://zenodo.org/badge/DOI/10.5281/zenodo.22080375.svg)](https://doi.org/10.5281/zenodo.22080375)

I am back from a trip to Ireland where I mostly circled around Galway. There, I stumbled upon a cheesemonger where I got to sample various flavours of Irish cheese. I was positively surprised, and ended up leaving with pieces of three varieties: Gubbeen, Carraignamuc, and **Carrig Bru**. I picked the latter, made from [Carrigaline cheese](https://en.wikipedia.org/wiki/Carrigaline_Farmhouse_Cheese) repeatedly washed with Irish ale, because the slate said it was made with "vegetarian rennet". The wheel looked plenty good, and I had yet to taste hard cheese made without traditional rennet. It tasted excellent and makes me wonder why I don't see more hard cheese using vegetarian rennet (though I suspect it's linked to the strict specifications required by the [_Protected Designation of Origin_][pdo]).

This new release of **cpp-sort** offers little compared to the months it spent in the making. Besides fixing decade-old bugs in features that apparently haven't ever been used by any single person before, it once again comes with work centered around [measures of disorder][measures-of-disorder]: a new measure, plenty more tests, and better documentation. Critically, the development follows the articles on my blog, [*The Sparkelling Bedangler*][sparkelling-bedangler], which is slowly becoming a better resource to understand the formal concepts around measures of disorder.

### New features

**New feature: [`probe::reve`][probe-reve]:** $\mathit{Reve}(X)$ is a new measure of disorder which I introduced [in a blog post][TSB012] some time ago, while attempting to prove that  $\mathit{Mono}(X) \le \mathit{Amp}(X)$ for any sequence $X$.

 $\mathit{Reve}(X)$ is defined as the number of changes (_reversals_) in the growth direction of a sequence $X$ when traversed linearly.

![Illustration of Reve over a small sequence of elements](https://morwenn.github.io/assets/images/TSB012/plot-reve.png)

It is equivalent to $\mathit{Mono}$ because $\mathit{Mono}(X) \le \mathit{Reve}(X) \le 2 \mathit{Mono}(X)$ for any sequence $X$. It is arguably less intuitive than $\mathit{Mono}$ in terms of sorting, but is a much more analyzed tool in the realms of mathematics: as a matter of fact, the number of permutations for which $\mathit{Reve}(X) = k$ follows the OIES sequence [A059427][OEIS059427], which has plenty of appearances in the literature.

I hope that this alternative definition will eventually unlock new insights in the analysis of $\mathit{Mono}$, and its relations with other measures of disorder.

### Bug fixes

* Fixed [`weak_less` and `weak_greater`][comparators-weak-order] when applied to floating-point numbers. They never worked, but used to be untested. Adding tests revealed the bug.
* Fixed a similar issue with [`partial_less` and `partial_greater`][comparators-partial-order].

### Improvements

Algorithmic & speed improvements:
* [`sorting_network_sorter`][sorting-network-sorter]: sorting 26 inputs now requires 139 *compare-exchanges* instead of 138 thanks to a new network found by [SorterHunter][sorter-hunter].

Other improvements:
* [`total_less` and `total_greater`][comparators-total-order] now use [`std::strong_order`][std-strong-order] when available to compare floating-point numbers, which correctly implements the IEEE *totalOrder* operator. The fallback implementation still cannot differentiate NaNs besides their sign.
* The fallbacks from [`weak_less`, `weak_greater`][comparators-weak-order], [`partial_less` and `partial_greater`][comparators-partial-order] to a stricter order when the customization point overload resolution fails are now marked `constexpr`.

### Tooling

Documentation:
* [Measures of disorder][measures-of-disorder]:
  * Correctly document when the result of an integer division is expected to be floored.
  * Add an illustration for [`probe::mono`][probe-mono].
  * Mentio…

Share this resource