1.17.1 — Angel Drops

This is the last scheduled release of the branch 1.x.y of cpp-sort. I named it after the track Angel Drops by artist DUSQK, from their album 1991 Night Drive, which I have really had on repeat quite a bit lately. What happens next is that I might backport fixes and create patch releases in the future, but this C++14 branch won't see any active development unless there is explicit and well-motivated demand. In the meantime, this patch release brings some additional stability, mostly backported from v2.0.0.

Bug fixes

• Fix probe::osc.max_for_size(1) which used to return some garbage value.
• Fix probe::osc.max_for_size for even sizes: it used to unconditionally return $\frac{|X|(|X| - 2) - 1}{2}$, which is fine with odd sizes, but the actual bound for even sizes is $\frac{|X|(|X| - 2)}{2}$.

Miscellaneous

• Test suite: test all sorters with a "descending plateau" distribution: a strictly descending subsequence followed by a plateau of equivalent elements, followed by another strictly descending subsequence.
• Replace internal uses of std::is_trivial, deprecated in C++26.
• Documentation: clarify that probe::sus returns the minimum number of ascending subsequences that can be used to decompose a sequence minus 1.
• Documentation: change Gollum command-line to display LaTeX math correctly.
• Require at least CMake 3.5.0 everywhere, to keep CI builds working for a bit longer.
• Bump downloaded version of Catch2 to v3.10.0.
• Bump downloaded version of libassert to v3.9.1.
• Add probe::spear to the test_failing_sorter.cpp script.

v2.0.0 — Wheelbarrow

It's already been a whole decade since the inception of what would soon become cpp-sort, and it had accumulated a number of deprecated components over the years; it was high time to blow all that dust off with a breaking change. It was also a good opportunity to start requiring C++17: it's indeed been a very long time since I last had my hands on a compiler that did not support most C++17 features (even in continuous integration, which made guaranteeing support for older compilers more difficult). That change allows to get rid of a lot of internal polyfills—naturally leading to reduced maintenance effort—, and to slightly improve user experience here and there.

This release also focuses on improving the ecosystem around [measures of disorder][probes]: over the years, this project has become one of the first results when searching for "measures of presortedness", yet I was forced to admit that my own knowledge of the topic was extremely surface-level, and that the documentation was far from enough when not outright incorrect. Beyond clarifying the difference between the terms "measure of disorder" and "measure of presortedness", the wiki now clearly documents some important axioms and properties, what measures of disorder satisfy them, and how they relate to adaptive sorting. The test suite was made more robust in this area, with [RapidCheck][rapidcheck] being used to perform much more thorough tests of the different axioms, properties, lemmas and theorems from the literature. Special thanks to Slimane Benloucif for all the resources, enlightening conversations, and exchanges of points of views, without whom this release would have been much more tamer on this front.

Overall version 2.0.0 is almost solely focused on quality and making the project a better resource, without adding a single big new feature. Do not worry though, I do plan to bring back features to the table in the near future, with new sorters and measures of disorder on the way. Among my various goals, I would also like to add more safety-related features to the library, and to document some sorting-adjacent topics and implementation tricks from the library in a less rigid form [on my blog][the-sparkelling-bedangler]. What I do manage to work on will obviously depend on my motivation, though I do hope that leaving C++14 behind will help me with that.

Note: if you're an avid reading of the library's release notes, you might remember that I had been teasing a v2.0.0 breaking change for a long time, with ambitious changes. That effort is still undergoing, but does not correspond to the current version: I have hit a lot of road-blockers along the way, and progress has mostly stalled. I can't make any promise about a timeline, but as of today that future version targets C++23.

Removals

cppsort::sort, cppsort::stable_sort and default_sorter (#168)

The very concept of cpp-sort is to put a handful of sorting-related algorithms and tools into the users' hands and to give them some amount of choice. Providing a default sorter kind of went against that, and the one I picked at the time was supposedly "best effort" but truly ad-hoc, likely not answering anybody's needs. Additionally it was a bloated mess, leading to measurable compilation slowdown and unreadable error messages.

If you feel nostalgic, you can still combine the bits and pieces yourself to bring back its spirit:

struct old_default_sorter:
    cppsort::self_sort_adapter<
        cppsort::hybrid_adapter<
            cppsort::small_array_adapter<
                cppsort::low_comparisons_sorter,
                std::make_index_sequence<14u>
            >,
            cppsort::quick_sorter,
            cppsort::pdq_sorter
        >
    >
{};

template<>
struct cppsort::stable_adapter<default_sorter>:
    cppsort::merge_sorter
{
    stable_adapter() = default;

    constexpr explicit stable_adapter(const default_sorter&) noexcept:
        stable_adapter()
    {}
};

cppsort::sort and cppsort::stable_sort (#167)

Despite looking cute and easy to use, these functions basically brought nothing to the table except a well-known interface for default_sorter, which got nuked as mentioned in the previous section. stable_sort was merely a wrapper hiding [stable_adapter][stable-adapter], and as such not much more useful. Both of the functions had heavy enough template tinkering to make overloads non-ambiguous, which happened to make compile times slower and error messages ever more unreadable when something went wrong.

In v2.0.0, the preferred solution is to use sorters and adapters directly.

drop_merge_sorter, split_sorter and verge_sorter

These sorters have respectively been replaced with [drop_merge_adapter][drop-merge-adapter], [split_adapter][split-adapter] and [verge_adapter][verge-adapter]. If you want the old sorters back, you need to explicitly wrap them as follows:

struct drop_merge_sorter:
    cppsort::drop_merge_adapter<cppsort::pdq_sorter>
{
    drop_merge_sorter() = default;
};

struct split_sorter:
    cppsort::split_adapter<cppsort::pdq_sorter>
{
    split_sorter() = default;
};

struct verge_sorter:
    cppsort:verge_adapter<
        cppsort::hybrid_adapter<
            cppsort::pdq_sorter,
            cppsort::quick_merge_sorter
        >
    >
{
    verge_sorter() = default;
};

template<>
struct cppsort::stable_adapter<verge_sorter>:
    cppsort::stable_t<
        cppsort::verge_adapter<
            cppsort::hybrid_adapter<
                cppsort::pdq_sorter,
                cppsort::quick_merge_sorter
            >
        >
    >
{
    stable_adapter() = default;

    constexpr explicit stable_adapter(const verge_sorter&):
        cppsort::stable_t<
            cppsort::verge_adapter<
                cppsort::hybrid_adapter<
                    cppsort::pdq_sorter,
                    cppsort::quick_merge_sorter
                >
            >
        >()
    {}
};

Those reimplementations are also examples of how the existing components of the library compose.

block_sorter

The old block_sorter has been renamed to [wiki_sorter][wiki-sorter] a few versions ago. The reason behind that change is that block sorts are nowadays a class of sorting algorithms more than a single algorithm: [grail_sorter][grail-sorter] is another block sort, and many more have been invented in the last decade (many of them by members of the Discord server The Studio, @The-Studio-Discord), some of which differ widely in how they are implemented.

As such if felt unjust to keep the name "block sort" for a specific implementation thereof, especially since there is not one consensual "basic" block sort (unlike insertion, selection or heapsorts). Ironically enough, "wikisort" is also a bad name according to its author, who intended for his project to be "like a wiki around techniques to implement a block sort", but that's what the algorithm is generally called nowadays.

counting_adapter

This old sorter adapter eventually gave birth to a subcategory of adapters with a slightly different interface: [metrics][metrics]. It can be replaced with [metrics::comparisons][metrics-comparisons], which similarly counts the number of comparisons performed by a comparison sorter.

Metrics are a category of sorter adapters meant to gather information about a sorter while it is running, that return the gathered information wrapped into [cppsort::utility::metric][metrics-tools]. As such, the main difference between counting_adapter and metrics::comparisons is that the latter returns utility::metric<CountType, comparisons_tag> instead of CountType.

probe::par

When I originally started adding measures of disorder to the library, I was discovering the very concept of disorder, and the literature around it at the same time. Most such measures had no implementation, neither in the paper nor in the wild, and the naming was pretty confusing. As a result lots of mistakes were made: along incorrectly implemented measures, I also accidentally implemented the same measure twice, under two different names: $Dis(X)$ and $Par(X)$. Those measures were introduced in different papers, but are fundamentally the same, as evidenced by Estivill-Castro, Mannila and Wood in Right invariant metrics and measures of presortedness.

A few years later as I was going through the literature and optimizing my implementation, I realized my mistake and removed $Par(X)$, reflecting the decision of Estivill-Castro and Wood to use the name $Dis(X)$ is all of their subsequent papers. It wasn't all for nothing: around the same time I added [a section to the documentation][probe-confusion] describing the various names under which different measures of disorder appear in the literature. It was after realizing that Altman and Igarashi described $Radius(X)$ in Roughly Sorting: Sequential and Parallel Approach, which I thought was a new measure of presortedness before realizing it was yet another name for $Dis(X)$ and $Par(X)$.

utility::static_const

static_const was a hack [originally used by Eric Niebler][static-const] to solve ODR issues while circumventing the lack of inline variables. We used it to create global instances of sorters:

namespace
{
    constexpr auto&& awesome_sort
        = cppsort::utility::static_const<awesome_sorter>::value;
}

With C++17 we get inline variables, which render static_const useless, hence its deletion:

inline constexpr awesome_sorter awesome_sort{};

utility::make_integer_range and utility::make_index_range

Old unused features that don't even interact with the rest of the library.

Other breaking chan...

1.17.0 — Seaweeds

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.

1.16.0 — Taxonomics

Over the last few months I spent much more time looking at plants and animals around me than I spent working on sorting algorithms, or working on any computer-related hobby project really. While I was trying to cleanup and finish this small new version — be it only to release the little work that had been done months ago —, I started thinking about using hierarchies inspired by biological taxonomy to classify algorithms. Imagine giving binomial names to algorithms: we might have a Sorteriformes order, with the big Partitionaceae and Mergeaceae families among others, Quicksortum hoareum and Quicksortum lomuto species, with their various optimized subspecies. Would radix sorts be part of the same order, or are they a case of convergent evolution? What would the global cladistic picture look like?

Anyway, for all the fun it might me, I have zero will to actually classify algorithms. That's a task I happily leave to others. In the meantime, please enjoy cpp-sort 1.16.0 for what it brings!

Deprecations

counting_adapter is now deprecated, metrics::comparisons should be used instead.

Deprecated components will be removed in cpp-sort 2.0.0.

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

New features

New metric: metrics::moves: it computes the number of moves performed when sorting a collection. The current implementation is fairly primitive with a number of limitations:

• It allocates a contiguous memory buffer of a special type to work, so if a sorter behaves differently based on the iterator category, only its behavior over contiguous iterators will have its number of moves counted.
• Sorters that call operations specific to some types might return a result that is not representative of how they actually perform: this is due to the inner wrapper type not benefiting from the specializations.
• Projection support is mandatory: metrics::moves passes a projection to the sorter in order to convert the wrapper type to its underlying type.
• Swap operations are not counted separately: the metric considers each swap operation to be three moves.

Some of these limits might be lifted or at least mitigated in the future.

Improvements

Algorithmic & speed improvements:

• poplar_sort's sift function was changed to use cycles of moves instead of swaps, cutting roughly in half the number of moves performed by the algorithm in the average case. It makes little difference for primitive types from a speed point of view, but might be noticeable when types become more expensive to move.
  

Other improvements:

• Bump downloaded version of libassert to v1.2.2.
• metrics::comparisons and metrics::projections now honour is_probably_branchless_comparison and is_probably_branchless_projection respectively: they pretend to be branchless when the wrapped callable is branchless, in order to better represent how many times said callable would be called — they will now report more accurate results for algorithms that change strategies based on branchlessness.

Tooling

Documentation:

• I recently realized that the implementation of partition for forward iterators used a Lomuto partition scheme, which runs in O(n) time. For some reason I had wrongly assumed that partition ran in O(n log n) time for forward iterators. The documentation for algorithms relying on partition over forward iterators was consequently updated as follows:
  • quick_merge_sorter runs in O(n log n) time on forward iterators instead of O(n log² n) time.
  • quick_sorter runs in O(n log n) time on forward iterators instead of O(n log² n) time.
• Add complexity tables to the documentation of drop_merge_adapter and split_adapter.
• Remove or replace references to deprecated features when possible.

Benchmarks:

• The cpu_cycles metrics helper can now be converted to a function pointer when empty.
• The inversions benchmark was moved to a presortedness directory, and tweaked with the goal of making it easier to use to see how different sorting algorithms fare when generating sequences with different kinds of presortedness.
• A new script was added to that new presortedness directory to plot the accuracy of distributions that generate more or less disorder. knowing how a sorting algorithm behaves with regard to a specific measure of presortedness first requires being able to accurately generate a collection with the desired amount of disorder.
  
  As we can see in the graph above, dist::inv now produces an amount of Inv(X) close to the required one, but it is not perfect either in that regard.
• dist::inversions was renamed to dist::inv to better reflect that it is meant to create sequences with more or less Inv, and its implementation was changed to more accurately generate sequences with 0% to 100% inversions.
  
  The way that completion was implemented however shows in the graph above: the [0, 0.5] and [0.5, 1] ranges in dist::inv are implemented in such a way that Inv(X) keeps increasing (as per the previous bullet point), but they use two different algorithms and other measures of presortedness likely give a decreasing presortedness in the second half. If we plot insertion_sort against dist::inv, which is only Inv-adaptive, we can see that it gets slower as Inv increases in a pretty linear fashion:
  

Test suite:

• Fix Clang -Winvalid-utf8 warnings.
• Bump downloaded version of Catch2 to v3.6.0.

Miscellaneous:

• Branches master and develop have been replaced with branches 1.x.y-stable and 1.x.y-develop respectively, paving the way for a future 2.0.0 release.
• The conanfile.py that ships with the library now only works with Conan 2.0+. The packages available on Conan Center should still work with Conan 1.x.
• Add a minimal .clang-tidy file to the repository. Some diagnostics still fire as configured, it is not a goal to fix all of them right away.
• CI: make the communication with codecov more robust.
• CI: update MacOS runner image to macos-12, the older one being now deprecated.

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.

1.15.0 — An Mil

Last weekend I spent a whole day on a reconstituted village from year 1000 (An Mil in French) where a small documentary was shot. It was awesome and gave me enough motivation to finish this release 1.15.0 that spent waaaay too much time in the making.

One of the reasons it took so much time was that I wanted to implement metrics (issue #214) before releasing it and lost all motivation to work on the library whenever I tried to work on metrics. It prevented me from working on algorithm improvements because metrics were supposed to help me better assess said improvements. In the end this release only ships a very basic version of metrics and very few algorithmic improvements - in the future I will most likely only work on them again when I feel like it instead of needlessly blocking releases like I did this time. At the end of the day, it is a hobby project and I can only gather so much motivation.

Deprecations

The following sorters are now deprecated as more generic features have been introduced to replace them:

• drop_merge_sorter: use drop_merge_adapter<pdq_sorter> instead.
• split_sorter: use split_adapter<pdq_sorter> instead.
• [verge_sorter][verge-sorter]: use [verge_adapter][verge-adapter]<pdq_sorter> instead for random-access iterators, or verge_adapter<quick_merge_sorter> for bidirectional iterators. The following composite sorter can be used as a drop-in replacement for the deprecated one:

  using verge_sorter = cppsort::verge_adapter<
      cppsort::hybrid_adapter<
          cppsort::pdq_sorter,
          cppsort::quick_merge_sorter
      >
  >

Deprecated components will be removed in cpp-sort 2.0.0.

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

New features

Metrics (issue #214)

Metrics are a special kind of sorter adapters that allow to retrieve information about the sorting process such as the number of comparisons performed when a collection is being sorted. This release ships the three following metrics:

• cppsort::metrics::comparisons: number of comparisons performed while sorting.
• cppsort::metrics::projections: number of projections performed while sorting.
• cppsort::metrics::running_time: time it took to sort the collection.

These adapters return an object of type [cppsort::utility::metric][utility-metric-tools], which is some kind of tagged value type. metrics::comparisons supersedes cppsort::counting_adapter, which will likely be deprecated in a future release.

New sorter: splay_sort implements splaysort, an adaptive O(n log n) comparison sort based on a splay tree data structure, a special kind of binary tree originally described by D. Sleator and E. Tarjan in Self-Adjusting Binary Search Trees.

The current implementation does not perform exceptionally well according to the benchmarks, though it might be improved in the future.

Support for libassert (experimental)

When the CPPSORT_USE_LIBASSERT macro is defined - and NDEBUG is not -, the library's internal assertions and audits use @jeremy-rifkin's libassert instead of the standard library assert to report failures, allowing better diagnostics in case of failure thanks notably to stack traces, expression decomposition and coloured console diagnostics. The CPPSORT_USE_LIBASSERT flag can also be passed to CMake.

That support is still experimental and might still contain undiagnosed issues.

Bug fixes

• Fixed construction of stable_adapter<hybrid_adapter<A, B, C>> with parameters. Because of an oversight, it could basically only be default-constructed.
• Additionally fixed stable_t<hybrid_adapter<A, B, C>>: stable_adapter<hybrid_adapter<A, B, C>>::type existed but could not be constructed from an instance of hybrid_adapter<A, B, C>. The ::type shortcut was therefore removed.

Improvements

Algorithmic & speed improvements:

• sorting_network_sorter now handles networks for 33 to 64 inputs. Many thanks @bertdobbelaere for the continued work on sorting networks on which most of this sorter is built.
• sorting_network_sorter: sorting 27 inputs now requires 147 compare-exchanges instead of 148 thanks to a new network found by SorterHunter.

Other improvements:

• [verge_adapter][verge-adapter] now works on bidirectional iterators. Prior to this release it only accepted random-access iterators.
• Defining CPPSORT_ENABLE_AUDITS now also automatically defines CPPSORT_ENABLE_ASSERTIONS.
• Fixed a warning that occurred when CPPSORT_ENABLE_AUDITS was defined but CPPSORT_ENABLE_ASSERTIONS wasn't.
• Fixed -Wpessimizing-move warnings in flip and not_fn with GCC 13.
• noexcept was added to several small functions in the library's internal code, occasionally leading to a better codegen.

Tooling

Benchmarks:

• Fixed a mistake that caused a compilation error in small-array benchmark since version 1.14.0.
• The inversions benchmark now uses heap_sort, drop_merge_adapter(heap_sort) and split_adapter(heap_sort), which are more interesting defaults for that benchmark than the previous ones.
• Replaced now deprecated [verge_sort][verge-sorter] with spin_sort in patterns benchmark.

Test suite:

• Fixed a bug with some old GCC versions in constexpr tests.
• Enabled more assertions when building the test suite: _GLIBCXX_ASSERTIONS with libstdc++ and _LIBCPP_ENABLE_ASSERTIONS with libc++.
• Bumped downloaded Catch2 version to v3.4.0.
• Do not compile with -Winline: the warning was extremely noisy on some platforms yet not really helpful. The library never explicitly tries to inline anything anyway, so the soundness of enabling that warning for the test suite was of debatable soundness.

Miscellaneous:

• Added two new CMake options: CPPSORT_ENABLE_ASSERTIONS and CPPSORT_ENABLE_AUDITS which control whether the macros of the same name are defined.
• Added the CMake option CPPSORT_USE_LIBASSERT to make assertions and audits use libassert instead of the standard library's assert.
• Upgraded CI from Ubuntu 18.04 to Ubuntu 20.04. This means that GCC versions older than 7 are not tested anymore.
• generate_sorting_network.py now directly consumes the JSON files from SorterHunter to generate networks.
• The whole Conan support was thoroughly updated: the embedded recipe now requires Conan 2.0 to work.

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.

[uti...

1.14.0 — Tantanmen

I am writing those lines shortly after coming back from the local ramen restaurant, where I had the pleasure to enjoy edamame and tantanmen for the first time in a while. After eight months and and two patch releases, the long-awaited cpp-sort 1.14.0 is finally out. One of the reasons already mentioned in previous release notes is the work on version 2.0.0, which is far from being ready, but already had a positive effect on the overall quality of the library.

Worry not, for this long time spent in the making was not in vain: this version brings more new features to the table than usual with a clear focus on orthogonality, allowing to make the most of existing features. Another highlight of this release is a focus on documentation: I tried to make it more amenable with new power words, a lots of small changes and also a new quickstart page.

New features

New adapters: split_adapter and drop_merge_adapter (#148)

[split_adapter][split-adapter]: the library has shipped [split_sorter][split-sorter] since version 1.4.0, a sorter base don an algorithm that works by isolating an approximation of a [longest non-decreasing subsequence][longest-increasing-subsequence] in a O(n) pass in the left part of the collection to sort, and the out-of-place elements in the right part of the collection. The right part is then sorted with [pdq_sort][pdq-sorter], and both parts are merged together to yield a sorted collection.

split_adapter is basically the same, except that it accepts any bidirectional sorter to replace pdq_sort in the algorithm. As such it acts as a pre-sorting algorithm that can be plugged on top of any compatible sorter to make it [Rem-adaptive][probe-rem].

[drop_merge_adapter][drop-merge-adapter]: this is the adapter version of [drop_merge_sorter][drop-merge-sorter], allowing to pass in any sorter instead of relying on [pdq_sort][pdq-sorter]. Much like SplitSort, [drop-merge sort][drop-merge-sort] works by isolating out-of-place elements, sorting them with another sorting algorithm, and merging them back together. Unlike SplitSort it places the out-of-place elements in a contiguous memory buffer, allowing to use any sorter to sort them.

While philosophically close from each other, the two algorithms use different heuristics to isolate out-of-place elements, leading to a different behaviour at runtime: for the same fallback algorithm, drop_merge_adapter is faster than split_sorter when there are few out-of-place elements in the collection to sort, but becomes slower when the number of out-of-place elements grows.

As can be seen in the benchmarks above, split_adapter and drop_merge adapter offer different advantages: split_adapter takes a bit less advantage of existing presortedness than drop_merge_adapter, but its cost it very small even when there are lots of inversions. This can be attributed to drop_merge_adapter allocating memory for the out-of-place elements while split_adapter does everything in-place.

When sorting a std::list however, drop_merge_adapter becomes much more interesting because the allocated memory allows to perform the adapted sort into a contiguous memory buffer, which tends to be faster.

New utilities: sorted_indices and apply_permutation (#200)

[utility::sorted_indices][sorted-indices] is a function object that takes a sorter and returns a new function object. This new function object accepts a collection and returns an std::vector containing indices of elements of the passed collection. These indices are ordered in such a way that the index at position N in the returned vector corresponds to the index where to find in the original collection the element that would be at position N in the sorted collection. It is quite similar to [numpy.argsort][numpy-argsort].

std::vector<int> vec = { 6, 4, 2, 1, 8, 7, 0, 9, 5, 3 };
auto get_sorted_indices_for = cppsort::utility::sorted_indices<cppsort::smooth_sorter>{};
auto indices = get_sorted_indices_for(vec);
// Displays 6 3 2 9 1 8 0 5 4 7
for (auto idx: indices) {
    std::cout << *it << ' ';
}

[utility::apply_permutation][apply-permutation] accepts a collection, and permutes it according to a collection of indices in linear time. It can be used together with sorted_indices to bring a collection in sorted order in two steps. It can even be used to apply the same permutation to several collections, allowing to deal with structure-of-array patterns where the information is split in several collections.

// Names & ages of persons, where the identity of the person is the
// same index in both collections
std::vector<std::string> names = { /* ... */ };
std::vector<int> ages = { /* ... */ };

auto get_sorted_indices_for = cppsort::utility::sorted_indices<cppsort::poplar_sorter>{};
auto indices = get_sorted_indices_for(names); // Get sorted indices to sort by name
// Bring persons in sorted order
cppsort::utility::apply_permutation(names, auto(indices));
cppsort::utility::apply_permutation(ages, indices);

Note the use of C++23 auto() copy above: apply_permutation mutates both of the collections it accepts, so the indices have to be copied in order to be reused.

New utilities: sorted_iterators and indirect (#42, #200)

[utility::sorted_iterators][sorted-iterators] is a function object that takes a sorter and returns a new function object. This new function object accepts a collection and returns an std::vector containing iterators to the passed collection in a sorted order. It can be thought of as a kind of sorted view of the passed collection - as long as said collection does not change. It can be useful when the order of the original collection must be preserved, but operations have to be performed on the sorted collection.

std::list<int> li = { 6, 4, 2, 1, 8, 7, 0, 9, 5, 3 };
auto get_sorted_iterators_for = cppsort::utility::sorted_iterators<cppsort::heap_sorter>{};
const auto iterators = get_sorted_iterators_for(li);
// Displays 0 1 2 3 4 5 6 7 8 9
for (auto it: iterators) {
    std::cout << *it << ' ';
}

The new projection [indirect][utility-functional] dereferences its parameter and returns the result. It can be used together with standard range algorithms to perform operations on the vector of iterators returned by sorted_iterators.

std::forward_list<int> fli = /* ... */;
auto get_sorted_iterators_for = cppsort::utility::sorted_iterators<cppsort::poplar_sorter>{};
const auto iterators = get_sorted_iterators_for(fli);
auto equal_bounds = std::ranges::equal_range(iterators, 42, {}, cppsort::utility::indirect{});

New sorter: d_ary_heap_sorter

[d_ary_heap_sorter][d-ary-heap-sorter] implements a heapsort variant based on a [d-ary heap][d-ary-heap], a heap where each node has D children - instead of 2 for a binary heap. This number of children nodes can be passed as an integer template parameter to the sorter and its associated sort function. Storing more nodes makes the algorithm a bit more complicated but improves the locality of reference, which can affect execution speed.

std::vector<int> vec = { /* ... */ };
cppsort::d_ary_heap_sort<4>(vec); // d=4

The complexity is the same as that of the library's [heap_sorter][heap-sorter]. It is however worth nothing that unlike its binary counterpart, d_ary_heap_sorter does not implement a bottom-up node searching strategy.

The benchmark above shows how the value picked for D might influence the speed of the algorithm. It also shows that [d_ary_heap_sort][d-ary-heap-sorter] is currently much slower than [heap_sort][heap-sorter], though the former is not really optimized and has room for improvements.

Bug fixes

• Fixed [slab_sort][slab-sorter] when sorting collections where several elements compare equivalent to the median element (#211).
• Fixed a potential use-after-move bug in [quick_merge_sort][quick-merge-sorter].

Improvements

Algorithmic & speed improvements:

• [slab_sort][slab-sorter] now falls back to using insertion sort on small enough collections in its melsort pass. This change leads to speed improvements when sorting shuffled data that does not exhibit obvious patterns.
  
• [low_moves_sorter<n>][low-moves-sorter]: removed O(n) comparisons in the generic case.
  

Other improvements:

• Add more [audit assertions][assertions-audits] around some internal merge operations. Audits are expensive assertions which can be enabled by defining the preprocessor macro CPPSORT_ENABLE_AUDITS.
• When CPPSORT_ENABLE_AUDITS is defined, the library's internal assumptions (e.g. __builtin_assume) are now turned into assertions, providing additional checks to diagnose errors.
• `schwarz_adapter<schwarz_adapter...

1.13.2 — Sword Search

This release is named after the eponymous song in the OST of The Legend of Zelda: Link's Awakening. This theme, following you for a short time at the very beginning of the game, never fails to haunt me and put me in a nostalgic mood, be it the original, the Switch remake or fan remakes. It's like the mood, the feels, the adventure are all still there deep down somewhere and forever.

This is the first cpp-sort version benefiting of a second patch release for a simple reason: I just made the library compatible with clang-cl. For those who don't know, clang-cl is a Clang fronted on MSVC, which also has the particularity of using the Microsoft STL instead of libc++. I only tested clang-cl recently, but I believe it worked in version 1.13.0 and I introduced a small change that broke it in version 1.13.0, hence a new patch version to fix that and introduce official support for this target.

Changes

No new features or algorithmic changes, this release is all about tooling:

• Make the test suite pass with clang-cl (#208). There are still lots of warnings, but they are mostly noise.
• Add clang-cl to continuous integration. Currently only the Debug mode is tested with clang-cl in the CI: the Release mode crashes due to what I think is an out-of-memory error in the VM, but I did compile & run it locally and it worked correctly.
• Improve std::identity detection with Clang and clang-cl in C++20 mode.
• Add a Python script to the tools folder to make it easier to change the version number where needed before a release.
• Make conanfile.py more compatible with Conan 2.0. It now requires at least Conan 1.50.0 to work.

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.

1.13.1 — Find Her

This release is named after Easily Embarrassed's critically underrated Find Her, a great mix of bounce, crispy synths and glitchy sounds. It seems that I can't ever get bored of it.

I haven't taken the time to work a lot on cpp-sort lately, which called for at least a small release with the available bug fixes and quality of life changes. While remaining mostly a quality-of-life release, it eventually turned out to be bigger than expected, mostly due to the ongoing work the future version 2.0.0 of the library and the resulting refactors and backports.

The most notable changes are the algorithmic improvements mentioned in the corresponding section of this note, and the addition of a page explaining how to write a sorter adapter to the documentation.

Bug fixes

• Fix iter_move and iter_swap when the library is compiled with C++20. The standard perimeter changed a bit in this area, and caused some ambiguous overload errors when the compiler couldn't decide which overload to pick between the standard library ones and the cppsort::utility:: ones. The standard library ones are now preferred for standard types when they exist.
• <cpp-sort/sorters/spreadsort/string_spread_sorter.h> could not be included alone due to a missing include. This is now fixed.
• Fix a bug where make_projection_compare failed to compile when passed an instance of std::identity in C++20 mode. Introduced in version 1.13.0, this bug could cause issues when passing std::identity to sorters relying on sorter_facade to provide projection support, such as std_sorter.

  // Error in 1.13.0, works in 1.13.1
  cppsort::std_sort(collection, std::greater{}, std::identity{});

Improvements

Algorithmic & speed improvements:

• Update heap_sort from upstream (we use the libc++ implementation): the new implementations turns it into a bottom-up heapsort. It performs fewer comparisons than the previous implementation, which doesn't make a noticeable difference from a speed point of view when comparisons are cheap, but can be much more noticeable when comparisons are expensive. This new implementation can be slower in the expensive moves/cheap comparisons scenario.
  
• The fallback of quick_merge_sort for forward iterators when sorting just a few elements was changed from bubble sort to selection sort after I was reminded of the fact that quick_merge_sort was not a stable sort anyway and could therefore switch to a better unstable fallback algorithm for very small collections.
  
• string_spread_sort was changed to perform fewer projections, sometimes halving the total number of performed projections.
  
• The library's internal adaptive quickselect implementation was tweaked to perform fewer projections. As a result the following sorters perform up to 1% fewer projections when operating on random-access iterators:
  • quick_merge_sorter
  • slab_sorter
• MSVC STL SIMD algorithms are now used when possible, which might marginally impact the following components for random-access iterators:
  • grail_sorter
  • merge_insertion_sorter
  • merge_sorter
  • quick_merge_sorter
  • slab_sorter
  • spin_sorter
  • split_sorter
  • tim_sorter
  • verge_sorter
  • wiki_sorter
  • verge_adapter

Improvements to sorting networks:

• All sorting networks used by sorting_network_sorter are now formally verified.
• Regenerate all sorting_network_sorter specializations with the smallest networks from this list. The main resulting change is that sorting 25 inputs is now done with 130 compare-exchanges instead of 131.
• All specializations of sorting_network_sorter now have their index_pairs() function marked as [[nodiscard]] when possible.

Other improvements:

• Total, weak and partial order comparators now support __int128_t and __uint128_t.
• hybrid_adapter is now fully constexpr when the sorters it wraps are themselves constexpr (#58).

Tooling

• Add a tutorial to the documentation explaining how to write a sorter adapter with a simple example (issue #154).
• Various smaller changes to improve the overall quality of the documentation.
• The required and downloaded Catch2 version is now v3.1.0.
• The generate.py from the tools directory was changed by a more complete generate_sorting_network.py tool which formally verifies that a given sorting network works, then generates the corresponding sorting_network_sorter.
• dist::as_long_string in the benchmarking tools now inherits from utility::projection_base and its operator() is const.
• Continuous integration: update scripts to use actions/checkout v3.
• The configurations tested by the CI change depending on which tools are available in the CI environments.

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.

1.13.0 — Swimming Pool

A few days ago I went to the swimming pool for the first time since 2015, which might also be the first time since the very first cpp-sort commits. The library is getting old, and while it might be too late to give it a cute name, it is still time to give it a cute logo.

This release focuses on improving the state of function objects in the library in a somewhat holistic way, notably with the addition of flip and not_fn, but also with smaller changes:

• Many more function objects are now transparent or conditionally transparent.
• Several function objects that except a single parameter now inherit from projection_base, which makes them more easily chainable.
• Some comparator adapters were updated to automatically unwrap upon recognizing specific function objects, allowing to reduce template nesting and instantiations.
• The documentation about function objects and related concepts was improved.

New features

New comparator adapters not_fn and flip. The former is equivalent to the C++17 std::not_fn: it takes a comparator and returns a function object of type not_fn_t<F> whose call operator calls the adapted comparator and returns the negation of its result. The latter is named after the flip function from Haskell's Prelude module: it takes a comparator and returns a function object of type flip_t<F> whose call opearator calls the adapted comparator with its arguments flipped. Here is an example of them being used to reimplement std::upper_bound in terms of std::lower_bound:

template<typename ForwardIt, typename T, typename Compare>
auto upper_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp)
    -> ForwardIt
{
    return std::lower_bound(
        first, last, value,
        cppsort::not_fn(cppsort::flip(comp))
    );
}

The function templates flip and not_fn recognize and unwrap some combinations of flip_t, not_fn_t and other "vocabulary types" in function objects. For example flip(flip(std::less{})) returns an instance of std::less<> instead of flip_t<flip_t<std::less<>>>. The goal is to reduce the nesting of templates as well as the number of templates instantiated by the library — which is especially interesting considering that many of the library's internal functions rely on flip and not_fn.

New sorter: adaptive_shivers_sort, a k-aware natural mergesort described by Vincent Jugé in Adaptive Shivers Sort: An Alternative Sorting Algorithm. It is very similar to tim_sort and actually shares most of its code. Adaptive ShiversSort worst case notably performs 33% fewer comparisons that timsort's worse case.

Bug fixes

• When wrapping a non-comparison sorter that accepts projections (such as spread_sorter), indirect_adapter failed to compile if passed a projection but no comparison (issue #204, thanks to @marc1uk for reporting).

Improvements

• sorting_network_sorter now uses one fewer compare-exchange than previously for 21, 22, 23, 25, 27 and 29 inputs thanks to the latest results of SorterHunter.
• The following function objects from <cpp-sort/utility/functional.h> are now unconditionally transparent and inherit from projection_base:
  • utility::half
  • utility::log
  • utility::sqrt
• The objects returned by as_comparison and as_projection as well as the result of chained projections are now transparent when their parameters are also transparent.
• The objects returned by make_projection_compare, as_comparison and as_projection are now default-constructible when the adapted function objects are default-constructible.
• make_projection_compare now returns the passed comparison directly when the passed projection is std::identity or utility::identity. This change can help to reduce the number of template instantiations in generic code. This is potentially a minor breaking change.
• Silence a -Wunused-but-set-variable false positive in pdq_sorter which fired with some versions of MinGW-w64.

Tooling

Documentation:

• The documentation now uses relative links when linking to its own pages instead of absolute links to the online wiki. This makes the documentation more easily browsable in the GitHub repository interface at any point in time.
• It is also now browsable offline with Gollum (issue #198). A new section of the documentation explains how to do it.
• Update the documentation about comparators, create a dedicated page comparator adapters.
• Add a section explaining what transparent function objects are.

Test suite:

• Rename the test suite directory from testsuite to tests, in accordance with the Pitchfork project layout.
• Upgrade Catch2 to v3-preview4.
• New CMake option CPPSORT_STATIC_TESTS: when ON some tests are turned into static_assert and are reported as success if the program compiles. The option defaults to OFF.
• New wiki section to document the concept of transparent function objects.
• Give the [comparison] tag to more tests, unify similar tags.
• Move every_sorter_* tests from the root of the test suite to the sorters subdirectory.

Miscellaneous:

• The project layout is now fully compatible with the Pitchfork project layout.
• Bump codecov-action to v3.
• The action to deploy the documentation to the wiki was updated to stop relying on the unmaintained SwiftDocOrg/github-wiki-publish-action.

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.

1.12.1 — Till It's Over

This release is named after Tristam's timeless glitch hop classic Till It's Over, which is always a favourite of mine when I want to be pumped up while programming — or doing anything else, really.

This end-of-the year release mostly fixes bugs and warnings, but also delivers a few small improvements to the library and its tooling that were ready and unlikely to cause issues. Notably sorters and adapters should now be able to handle some iterators even when they define a difference_type smaller than int.

Bug fixes

• counting_sorter::iterator_category and counting_sorter::is_always_stable were accidentally unavailable since version 1.9.0 unless __cpp_lib_ranges was defined. They are now unconditionally available again.
• Due to a missing using declaration, slab_sort only compiled for iterators with an ADL-found iter_swap.
• Fix compile time error in quick_sort when the passed iterators have a difference_type smaller than int.

Improvements

• slab_sort now works with bidirectional iterators.
• drop_merge_sort does not need to compute the size of the collection anymore, which saves a full pass over the collection to sort when with bidirectional iterators.
• Reduce the number of memory allocations performed by spin_sort.
• utility::size now also works with collections that only provide non-const begin() and end() functions.
• Fix warnings in the following sorters due to integer promotion issues when the passed iterators have a difference_type smaller than int:
  • merge_insertion_sorter
  • poplar_sorter
  • spin_sorter

Tooling

• Rollback changes to the patterns benchmark accidentally committed in version 1.12.0.
• Rewrite large parts of the bubble sort tutorial.
• Test sorters and adapters with an iterator type for which difference_type = std::int8_t.

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.