1.8.1 — Lavender Town

It's spooky month in Pokémon Go, and as a result I've found myself listening to several remixes of the Lavender Town theme - an all-time favourite of mine - while preparing this release. Consider it project culture now that bugfix releases are named after songs since I can't wait for something specific to happen to me to name those (which is something I tend to do with other releases).

The release itself is mostly a number of bug fixes, documentation fixes and tiny improvements. Most of those were the result on working on several smaller sorting-related projects that share some code with cpp-sort.

Bug fixes

• Change the loop condition in the minRunLength() function in the tim_sorter implementation so that it matches the one in CPython (issue #172, thanks @weeyizhi).
• Fix the iterator_category of quick_merge_sorter.
• Fix the complexity of quick_sorter and quick_merge_sorter for forward iterators in the documentation.

Improvements

• Fix the implementation of the Tukey's ninther used for pivot selection by quick_sorter and quick_merge_sorter. A bug in the elements being swapped meant that a value further away from the median was picked sometimes. It is unknown whether this was sufficient to change the complexity of the algorithm, but no significant difference in speed was noticed after the change.
• The bidirectional iterators version of verge_sorter now returns early if the collection is already sorted.
• poplar_sorter was tweaked to ensure that it only ever performs a single memory allocation to track the poplars.

Tooling

• Specifically download Catch2 v2.13.2 when no suitable version of Catch2 is found on the system. This is technically a bugfix since the master tag was use so far for the download, and it was recently removed from the repository.
• The conanfile.py now raises a ConanInvalidConfiguration error when the target compiler does not support C++14.
• Update the original research page of the wiki with up-to-date information.
• Add a checklist of tasks to perform when releasing a new version of the library. This should prevent some issues that commonly occur while preparing a release.
• Change the Conan badge in the README to point to the new Conan Center website.

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.8.0 — Mochis

I have started cooking a bit more during the confinement, and I've recently made a bunch of mochis, which were some of the delicacies I missed the most from the trip in Japan. I've also cooked some Japanese curry and increasingly improved instant noodles, but mochis were more of a symbol. My taste buds are satisfied, it's time for a new cpp-sort release.

This release brings no new feature, but improves the existing ones a lot, and deprecates a few. Special care was given to the algorithms that support forward and bidirectional iterators, many of whom were a bit neglected or suffered from excessive pessimization. The other big things in this release are the improvements in tooling. You can read more about it below, but here is the gist of it:

• The wiki pages are now in the main source repository, and a GitHub Action automatically updates the wiki when a new release is created.
• New benchmarks were added to display interesting properties of some algorithms.
• The [Benchmarks][wiki-benchmarks] page of the documentation was totally rewritten, and all benchmarks were regenerated to be up-to-date with the library.

Deprecations

The following features are now deprecated and will fire deprecation warnings if used. They will be removed in cpp-sort 2.0.0 (see the linked issues for the rationale for deprecation & removal):

• cppsort::default_sorter (#168): replace with [pdq_sort][pdq-sort] or a carefully chosen sorter.
• cppsort::sort (#167): replace with [pdq_sort][pdq-sort] or a carefully chosen sorter.
• cppsort::stable_sort (#167): replace with [merge_sort][merge-sort], or wrap a sorter in [stable_adapter][stable-adapter].
• [cppsort::make_integer_range][make-integer-range]: this utility hasn't been used since 2015 and does not help with any of the library's components.

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

Bug fixes

• Add missing includes to [out_of_place_adapter][out-of-place-adapter] that sometimes triggered compile time errors.
• The declared iterator_category of [out_of_place_adapter][out-of-place-adapter] is now always std::forward_iterator_tag, in line with what the documentation claimed.
• Fix bug that sometimes occurred when [sorter_facade][sorter-facade] was used to add projections support to an algorithm that only handles comparisons. This might fix issues with [std_sorter][std-sorter].
• Fix bugs due to use of moved-from comparison and projection functions in [probe::exc][probe-exc], [probe::ham][probe-ham] and [probe::max][probe-max].
• Fix construction of [stable_adapter][stable-adapter]<[std_sorter][std-sorter]> from an instance of std_sorter. It mainly makes it more usable with C++17 implicit deduction guides.

Improvements

• [indirect_adapter][indirect-adapter] now also works with forward and bidirectional iterators (#166). The algorithm underlying these new capabilities is Matthew Bentley's [indiesort][indiesort]. The resulting sorter can sort any iterator category regardless of the iterator category of the adapted sorter.
• When given forward iterators and when no extra heap memory is available, [merge_sort][merge-sort] is now globally faster than it used to (see the story here if you want fun trivia):
  
• When given forward iterators or bidirectional iterators, [probe::dis][probe-dis] is now O(n²) instead of accidentally being O(n³), leading to ridiculously huge improvements:
  
  The algorithm was further improved with a heuristic allowing it to short-circuit non-negligible parts of the computation when it doesn't hit one of the worst cases:
  
  In the graph above probe::dis-dev corresponds to probe::dis in the previous graph - the color was kept for consistency. It is also worth nothing that the collection used is 10 times the size of the one used for the previous graph.
• Other sorters, adapters, measures of presortedness and internal algorithms that handle forward and/or bidirectional iterators used to start by computing the size of the passed collection, which was often rather sub-optimal (#169). Those components were reviewed prior to this release, and changed as needed. They now perform O(n) fewer operations when passed a collection which provides its size in O(1), leading to speed improvements in the following user-facing function objects:
  • [probe::dis][probe-dis]
  • [probe::exc][probe-exc]
  • [probe::ham][probe-ham]
  • [probe::inv][probe-inv]
  • [probe::max][probe-max]
  • [probe::rem][probe-rem]
  • [schwartz_adapter][schwartz-adapter]
  • [stable_adapter][stable-adapter]
  • [verge_sorter][verge-sorter]
• The sorting network for 18 inputs uses fewer compare-exchange units than it used to thanks to the latest results of [SorterHunter][sorter-hunter].
• The sorting networks for 21 and 22 inputs also use newer results from [SorterHunter][sorter-hunter]. These networks don't have a smaller size than before, but have a smaller depth.
• The removal of cppsort::sort led to the change of the few parts of the library that relied on it. These lead to simpler error messages in those places.
• [verge_adapter][verge-adapter] had static assertions to ensure that the algorithm only handled forward iterators instead of bidirectional ones. This wasn't buggy per se but led to useless static assertions, and less clear error messages.

Tooling

Benchmarks:

• New benchmark to compare the evolution of the running times of different sorting algorithms when the size of the collection grows.
  
• New benchmark to visualize how the speed of some algorithms evolve with the number of inversions in the collection to sort.
  
• Some of the benchmarks now use a colorblind-friendly palette created by Thøger Rivera-Thorsen (unfortunately not the one above since it uses more colors than the new palette).
• The benchmarks directory was reorganized and now has one subdirectory per benchmark.
• patterns and small-array benchmarks now ensure that every sorter will be given the same input for random distributions, making the generated graphs more relevant.
• patterns now takes the root of the results directory as a command-line parameter instead of forcing it to profiles.
• patterns and errorbar-plot have an --alternative-palette option to switch to an infinite colour palette instead of the new default colourblind-friendly palette.
• small-array was enhanced with the experience gathered from the other benchmarks.
• Benchmarks now log the seed they were initialized with for better reproducibility.
• The benchmark distributions can now be passed a projection function to transform the generated size_t into any type in a custom way.

Documentation:

• The documentation sources are now in the main GitHub repository (#157), and a GitHub Action updates the wiki whenever something is pushed to master. This change makes things better in several ways:
  • Code, tests and documentation can be committed at the same time, increasing the coupling and making it easier to track or revert related changes.
  • It makes it easier for non-maintainers to contribute to the documentation.
  • It is now possible to have a specific version of the library with a matching documentation.
  • The day we switch to version 2.0.0, it will be possible to cleanup the documentation and having the doc for version 1.x and 2.x live side by side in different branches.
  • The documentation is now easily browsable for a given release or branch.
• The [Benchmarks][wiki-benchmarks] page was completely regenerated, updated with new benchmarks and reorganized. I hope that I will be able to keep it updated in the future.

Test suite:

• Additional tests for adapters that can handle forward iterators and/or bidirectional iterators.
• Test some [measures of presortedness][mop] when no heap memory is available.
• Additional tests to ensure that sorters and measures of presortedness don't use a moved-from comparison or projection.

Miscellaneous:

• New tool rename-library.py which renames all references to cpp-sort in the library, mainly used to test different versions of the library's algorithms side-by-side in benchmarks.
• All source files now use an UTF-8 encoding.
• The handling of licenses changed a bit: the way all the files are licensed now appears in a clearer way, there is NOTICE.txt file describing all the extra licenses, most files without an explicit license were changed to display one. Also source files now use a short form of the copyright notice in order to reduce the redundant per-file information.

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.7.0 — Flowers

I spent a great deal of time during the recent confinement identifying flowers and other plants in my garden, and I also learnt to cook some of them. I was left with a a few hundred plant pictures on my phone and decided to start a tiny glitch art side project with some of the flower photos. With all those flowery endeavours behind me, it was time to come back with a fresh cpp-sort release.

New features

Chainable projections through operator| have been implemented (issue #82), allowing to apply several transformations in a row when projecting a collection's element:

struct wrapper { int value; };
std::vector<wrapper> vec = { /* ... */ };
auto&& negate = cppsort::utility::as_projection(std::negate<>{});
// Applies &wrapper::value to the elements of vec, then negate
cppsort::split_sort(vec, &wrapper::value | negate);

The new operator| only considers classes inheriting from cppsort::utility::projection_base during overload resolutions. In order to make your own projections work with you can either make them inherit from projection_base, or adapt them with cppsort::utility::as_projection.

Improvements

• The speed of merge_insertion_sort has been improved (it remains an extremely slow algorithm):
  
  The old implementation used std::list internally, with either std::allocator or __gnu_cxx::bitmap_allocator when available to improve the allocation speed. The new implementation uses a custom list data structure which performs a single allocation of all the nodes required by the algorithm.
• Sorters and adapters now accept comparison functions that take their arguments by non-const reference, it is the responsibility of the caller to make sure that such predicates don't modify their parameters in a way that would affect the consistency of the sort (issue #136). Following the resolution of standard issue LWG3031 it is also the responsibility of the caller to ensure that, should the predicate accept both const and non-const parameters, the results are consistent between overloads.
• as_comparison and as_projection can now adapt any Callable, and not just objects callable with the normal function call syntax.
• Fixed an integer conversion warning in pdq_sort (merged a fix from upstream).
• Fixed a signed/unsigned warning in the measures of presortedness tests.
• Some compile time error stack traces might point directly into the cpp-sort algorithms instead of in standard library utilities, making them a bit shallower.
• Reduce the binary size of the code generated by ska_sort a bit.

Tooling

• CMake: Catch2 is now looked with find_package first, and only downloaded if no suitable version was found on the system. This notably allows to build the test suite while offline.
• CMake: Catch2 is not required anymore to build the examples.
• Fix the conanfile.py so that it works with the most recent Conan versions.
• Small improvements to bars.py in the benchmarking tools.

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.6.0 — Brunch

I didn't have the opportunity to brunch properly since my trip to Scotland back in August where I could enjoy tasty local breakfasts at unreasonable hours - with today's excellent vegetarian brunch that cycle is complete and I can publish a new cpp-sort release.

New features

A new spin_sorter has been added to the library, based on the algorithm from Boost.Sort. Spinsort is a stable mergesort derivative which is often faster than the other available stable sorting algorithms. It is a stable comparison sorting algorithm that runs in O(n log n) and requires O(n) additional memory; unlike other algorithms in the library it doesn't have a fallback when there isn't enough extra memory available to merge runs.

As can be seen in the benchmark result above (sorting a std::vector<long double> with 10^7 elements) it tends to be the fastest of the stable sorts for random data, and is otherwise adaptive when some presortedness exists in the data to sort.

Bug fixes

• Fixed a long-standing out-of-bounds issue in tim_sorter, which sometimes triggered Valgrind diagnostics when trying to sort an std::deque (issue #89).
• Fixed an ODR issue in hybrid_adapter that triggered a compile-time issue with Clang 9 (issue #158).
• Fixed an unsigned integer overflow in poplar_sorter that triggered a diagnostic with the undefined behaviour sanitizer.
• Fixed a static_assert that wasn't strict enough in verge_adapter.

Improvements

• The library doesn't have naked assert anymore: you now need to define the preprocessor flag CPPSORT_ENABLE_ASSERTIONS explicitly in order to enable assertions. This flag still honours the NDEBUG macro.
• When verge_sorter is used to sort bidirectional iterators, it now falls back to quick_merge_sorter instead of quick_sorter to sort sections of the data to sort where runs aren't big enough. This lowers the complexity from O(n²) to O(n log n log log n) with a worst case of O(log n log n) space - the complexity's worst case shifts from the fallback to the vergesort layer itself. The vergesort layer still uses O(n) memory when it finds patterns to optimize.
• counting_sorter is now able to sort collections of [un]signed __int128, even when the standard library is not properly instrumented to support them.
• Algorithms relying on uninitialized_move may be faster when sorting trivial types. Affected sorters: block_sorter, merge_insertion_sorter, merge_sorter, spin_sorter, tim_sorter and verge_sorter.
• Fewer copies of comparison and projection functions are performed when using stateful sorters.

Tooling

There has been some overarching CMake and Conan cleanups for this release: cpp-sort is notably available on Conan Center now, and the built-in Conan support has been reduced and should only be used by people willing to package their own version of the library.

• cpp-sort can now be used as a CMake subproject with add_subdirectory without triggering errors.
• New CMake option BUILD_EXAMPLES (OFF by default).
• CMake: fixed flags in Debug builds.
• Examples are now built during CI to avoid breaking them and forgetting about them.
• The wiki now has a section dedicated to tooling, which currently contains some information about the CMake and Conan integration of the library (issue #153).
• Improved test coverage for sorters that can handle forward and bidirectional iterators.
• Added tests to ensure that the library's algorithms marked as such can work even when no heap memory is available.
• Added tests for algorithms that special cases to handle int128.
• The releases should now be archived on Zenodo to make them easily citeable.

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.5.1 — Tiny Little Pieces

Tiny Little Pieces: it's both what was broken in the 1.5.0 release and the name of an excellent track by Hypnagog that I often listen to while programming.

Bug fixes

• Fix the constructor of hybrid_adapter, which failed for a variety of use cases, and notably when using CTAD in C++17. It now works as expected.

Improvements

• The constructor of hybrid_adapter taking sorters is now constexpr.
• All the overloads of adapter_storage::get() are now constexpr.

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.5.0 — Roadtrip

I spent the last two weeks enjoying a roadtrip through Scotland, watching the beautiful landscape while two good friends enjoyed driving the van on single-track roads. This feels pretty consistent with the previous Tartan release, and once again it gave me a boost of motivation to publish a cpp-sort release, so here we are.

New features

The highlight of this release is the ability for sorter adapters to accept stateful sorters: this is the first step required for supporting mutable sorters in the library (issue #104). This is useful to provide first-class support for sorters that are parametrized at construction time: for example imagine a counting_sorter taking min and max parameters at construction time to avoid having to look them up, it would still be possible to adapt such a sorter as follows:

auto sort1 = counting_sorter(0, 100); // NOT the cpp-sort sorter
auto sort2 = cppsort::out_of_place_adapter(sort1);
sort2(collection);

Several part of the library have been modified in order to support this feature. Here is an incomplete list of things that changed as a result:

• Most of the library's sorter adapters can now adapt stateful sorters out-of-the-box. One notable exception is small_array_adapter for which I was unable to come up with a satisfying design.
• Said sorter adapters now have a get() member function to retrieve a copy of the original sorter, except hybrid_adapter for which a single get() function wouldn't make sense since it adapts several sorters.
• These sorter adapters now also work with sorters that aren't default-constructible.
• sorter_facade was updated to handle stateful sorters: it can now be constructed with parameters which are forwarded to the sorter implementation, and it now only provides operators to convert the sorter to different of function pointers when said sorter is empty and default-constructible.

In order to work properly with sorter adapters, sorters are expected to be copy-constructible: adapters make a copy of the sorters they adapt. Additionally a sorter is expected to be empty and default-constructible for conversions to function pointers to work.

Under the hood, pretty much every single-sorter adapter inherits from the newly introduced utility::adapter_storage<Sorter> to store and retrieve the sorter they adapt. This class template implements three operations:

• Construction from a sorter: unless the passed sorter is empty and default-constructible, it copies the passed sorter into its internals.
• Retrieval of a sorter: if the sorter type it adapts is empty and default-constructible, then it returns a default-constructed instance of said sorter type, otherwise it returns a properly reference to the stored sorter whose const and reference qualifications depend on that of the adapter_storage instance.
• Invocation of the wrapped sorter: adapter_storage::operator() forwards its parameters to the corresponding operator in the wrapped sorter (or to a default-constructed sorter) and returns the result of that operation.

If you need to write a sorter adapter that properly handles stateful sorters, then inheriting from adapter_storage is probably the simplest solution to correctly provide the full gamut of semantics described above.

Bug fixes

• grail_sorter and tim_sorter now support comparison and projection function objects that aren't default-constructible.
• Fix codegen issue with MinGW-w64 GCC 9.1, which sometimes triggered a segfault when using quick_merge_sorter (issue #151).

Improvements

Function objects from the comparators module have been improved in the following ways (issue #150):

• The non-refined comparators are now transparent comparators: they have an is_transparent member type which allows them to be used in the standard library's ordered associative containers to compare heterogeneous types.
• The module now exposes explicit names for the main comparator types: total_less_t, total_greater_t, natural_less_t, etc. to make them more usable where type names are needed.
• natural_less is now able to compare heterogeneous types as long as they provide begin and end functions returning iterators that share a common value_type.

Other library improvements:

• Several out-of-place merge functions used in the library have been improved, which could make the following tools slightly faster: block_sorter, grail_sorter, merge_sorter, split_sorter, verge_sorter and verge_adapter.
• The internal move[_backward] algorithms have been rewritten to fallback to their std:: counterparts in more situations, which might make a good number of the library's algorithms faster when the std:: algorithms are optimized for specific iterators: this should notably be the case for libc++ std::deque iterators.
• Further small optimizations for grail_sorter and tim_sorter.
• If the global operator delete supports sized deallocation, then several allocating algorithms will take advantage of it.

Tooling

• The conanfile.py recipe is better integrated with CMake, and notably uses the project's CMakeLists.txt install rules to package the library.
• The generated CMake package version file is now architecture-independent.
• The sanitizers should now fail fast when expected to.
• The Windows builds now correctly work with incremental compilation in Travis.

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.4.0 — Tartan

It was Tartan Day a few days ago, the perfect occasion to wear your kilt or anything tartan. Combined with a surprise carbonade flamande with a friend over the weekend, I had all the energy required to finally fix a remaining bug and push a new cpp-sort release.

This release brings a single new feature, split_sorter that we will describe later, and a bunch of bug fixes, tiny library improvements, and tooling improvements. The development was somewhat painful because benchmarking split_sort lead me to an existing bug in drop_merge_sort, so I analyzed it, fixed it, wrote a more general test and found bugs in other sorting algorithms, then in measures of presortedness, and even in tooling while I was doing further testing... The rabbit hole went ever deeper, but it eventually came to an end and I could finally produce that single-feature release.

New features

A split_sorter has been added to the library, implementing the "in-place" variant of the SplitSort algorithm described in Splitsort—an adaptive sorting algorithm by Levcopoulos and Petersson. split_sort is a comparison-based unstable sorting algorithm that might require O(n) extra memory to speed up an internal merge step, but works fine with O(1) extra memory nonetheless.

The algorithm is close from drop-merge sort: it computes an approximation of a longest non-decreasing subsequence, excludes the elements that are not part of it, sorts them (currently with pdqsort), and merges the two sequences. The graph below shows how it performs compared to drop-merge sort when sorting a collection with an increasing number of elements not in their place:

While it shares many similarities with drop-merge sort, they still have a few differences:

• SplitSort only works with random-access iterators.
• While it uses O(n) extra memory to merge some elements, it can run perfectly fine with O(1) extra memory. Drop-merge sort on the other hand won't work with O(1) extra memory.
• The results above show that drop-merge sort is better when few elements aren't in place, but SplitSort has a lower overhead on random data while still performing better than most general-purpose sorting algorithms when the data is already somewhat sorted.

split_sort offers a tool similar to drop_merge_sort, but with different tradeoffs.

Bug fixes

• The measures of presortedness exc, ham and max now correctly handle duplicate values (#143).
• Fixed issues due to self-move in the following algorithms (#141): block_sort and drop_merge_sort.
• Fixed sorting of non-SSO-optimized std::string with the following algorithms (#142): block_sort, drop_merge_sort and grail_sort.

Improvements

• Nested hybrid_adapter now automatically unwraps (thanks to @notfoundry for this!). To understand why this feature is interesting, consider the following sorter:

  using sorter = cppsort::hybrid_adapter<
      cppsort::hybrid_adapter<
          forward_sorter,
          random_access_sorter
      >,
      bidirectional_sorter
  >;

  When called on forward or bidirectional iterators, sorter will use the appropriate sorter. However, without the unwrapping, sorter can never call random_access_sorter because the outer sorter considers the iterator category of the inner sorter, which in this case is std::forward_iterator_tag. With the new unwrapping ability, the sorter above should be equivalent to the following one:

  using sorter = cppsort::hybrid_adapter<
      forward_sorter,
      random_access_sorter
      bidirectional_sorter
  >;

  Therefore it will call random_access_sorter as expected when passed random-access iterators.

• Avoid Clang -Wc++1z-extensions warnings when using [[fallthrough]] while not in C++17.

• Small optimizations in block_sort, drop_merge_sort, grail_sort, schwartz_adapter and tim_sort.

• schwartz_adapter now simply calls the adapted sorter when passed identity as a projection.

Tooling

Some efforts were made to improve the build times, notably because of the increasingly high build times of the continuous integration:

• Use mtime_cache on the CI server to finally have proper incremental builds.
• When building on Linux with Clang, the testsuite now uses LLD for linking.
• Only download relevant packages needed for each build in Travis.

Other tooling changes:

• The testsuite is now tested on Windows with a 64-bit MinGW-w64 on the CI server.
• The testsuite doesn't use cotire anymore since it didn't seem to make a difference in build times.
• We now define proper flags for warnings depending on the compiler when building the testsuite.
• More tests to cover more potential issues.
• Fix several issues with the CI reporting failing tests as passing (most notably with ubsan and Valgrind).
• Ship a suppression file to avoid Valgrind false positives with OSX on the CI server.
• Add a small tool - test_failing_sorter.cpp - which I often use and tweak to investigate failing sorters.

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. I still don't have a great version hygiene for those, but I promise that it will improve with the time.

1.3.0 — Cuddles

I legit had the best cuddles in my life over the weekend (it's never too late to learn new things apparently), so I am now in a good mood to finish a cpp-sort release ^^ This new release doesn't offer new features on the library side, but the CMake scripts have been totally overhauled to take advantage of modern CMake features and provide a cleaner interface.

New features

Overhaul of the CMake scripts:

• Switch to use the target system instead of of the old directory system.
• cpp-sort now exports a CMake target.
• Catch2 is now downloaded at configure time instead of build time, which allows to properly link to the Catch2::Catch2 CMake target. This uses the CMake script Crascit/DownloadProject.
• Use catch_discover_test to have one CTest test per Catch2 test instead of one CTest test for the whole testsuite.
• Run CTest tests in parallel now that there are many.
• Use CTest built-in features to run Valgrind.

Bug fixes

• Fix fixed_buffer<0> which miscompiled with Clang 6.
• probe::mono didn't work when the comparison function was a special kind of callable (e.g. a pointer to member).
• out_of_place_adapter sometimes didn't work because we accidentally let ADL find a function in an inner namespace instead of fully qualifying it (which was enough for the testsuite).

Improvements

• The sorting networks for 23, 24, 25 and 26 inputs use fewer compare-exchange units than they used to thanks to the latest results of SorterHunter.
• schwartz_adapter now returns the result of the adapted sorter if any when called (#134).
• indirect_adapter and out_of_place_adapter now return the result of their adapted sorter if any when called (C++17 only, depends on the feature test macro __cpp_lib_uncaught_exceptions) (#134).
• indirect_adapter now works with projection-only sorters too (e.g. ska_sorter, spread_sorter) (#138).
• Make the internal algorithms lower_bound and upper_bound somewhat faster, helping to make many algorithms using them slightly faster.

Tooling

• The tool to validate sorting networks has been parallelized and now runs a few times faster.
• Use the CMake script cotire to hopefully improve the build times.
• Use Catch2's new TEMPLATE_TEST_CASE to significantly reduce the size of the code of the testsuite.

1.2.0 — Freckles

I've recently got my freckles-ridden skin checked for melanomas and I apparently don't have any, which is an excellent occasion to celebrate with a new cpp-sort release. This release brings new tools and several performance improvements to the library.

New features

• New sorter: quick_merge_sort. It is a specific flavour of the QuickMergeSort algorithm proposed by Stefan Edelkamp and Armin Weiß with a specific quirk: it starts by partitioning the collection with an equivalent of std::nth_element at its two thirds, then uses an internal mergesort to sort the first two thirds, using the last part of the collection as a swap buffer, then proceeds to sort the last third with the same technique. This sorter runs in O(n log n) even with forward iterators, using at most O(log²n) stack memory due to recursion.
• New sorter adapter: out_of_place_adapter. This adapter simply moves the elements of the collection to sort to a temporary buffer, sorts the buffer with the adapted sorter, then moves the sorted result back to the original collection. As long as enough memory is available, it is the easiest way to sort a collection providing forward or directional iterators fast enough, allowing to use random-access sorters to sort them in the temporary buffer.

Bug fixes

• Apply spreadsort bug fix from boostorg/sort#26

Improvements

• quick_sorter is now guaranteed to run in O(n log n) instead of O(n²). In order to achieve this it uses the median-of-medians algorithm to select its pivot when the recursion exceeds 2log n. This brings the space complexity up to O(log²n) due to the stack space used by the mutual recursion of the median-of-medians algorithm.
• sorting_network_sorter now needs 100 comparisons instead of 101 to sort 21 inputs thanks to the latest results of SorterHunter.
• When there isn't enough memory available, the random-access overload of the inplace_merge function used by several sorters now uses the Symmerge algorithm described by Pok-Son Kim and Arne Kutzner in Stable Minimum Storage Merging by Symmetric Comparisons instead of the old Dudziński and Dydek algorithm.
• tim_sorter now reuses a same merge buffer — making it grow as needed — instead of reallocating and deallocating a new buffer whenever it needs to merge runs.
• ska_sorter is now able to sort collections of [un]signed __int128, even when the standard library is not properly instrumented to support them.
• stable_adapter<hybrid_adapter<Sorters...>> is now equivalent to hybrid_adapter<stable_adapter<Sorters>...> in order to better take advantage of sorters and adapters specialized for stable_adapter.
• The library is now C++20 compatible: the library parts removed in C++20 have been replaced by hand-rolled ones.
• Several small changes to reduce template instantiations in different places.

Tooling

• Make it easier to change the type of elements to sort in bench.cpp.
• The tool to validate sorting networks is a bit faster thanks to a new permutation algorithm based on Gray codes.

1.1.1 — Japan

I will be away in Japan for a few weeks, which means that it is probably a good time for a bugfix release. No new exciting feature in this release, but several small improvements here and there.

Bug fixes

• Work around a Clang bug to fix the implicit deduction guide of counting_adapter in C++17
• Add missing constructor to stable_adapter<self_sort_adapter> to make implicit deduction guides work in C++17
• Fix warning about class/struct difference between declaration and definition of hybrid_adapter

Tiny improvements

• Make the constructors of sorter adapters taking one or more sorters explicit
• probe::rem now performs a single pass over the sequence even when passed non-random-access iterators, which might make it slightly more performant in this case
• Code using std::result_of now uses std::invoke_result when available, making it more robust against type system subtleties
• More noexcept here and there
• Tiny attempts to improve the build times and produced binary size here and there, but it unfortunately shouldn't make any noticeable difference