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

1.1.0 — New job

This release doesn't bring many new things into cpp-sort, but has a few worthwhile bug & consistency fixes. I got a new job, hence the release name, and wanted to push everything that was ready because I might not be as active on the project for some time.

There were a few global efforts to reduce unneeded template instantiations, reduce the produced binary size and improve compile times a bit, but these changes are anecdotal at best, and probably don't make a noticeable difference.

New features

• New measure of presortedness: probe::mono, after the equivalent Mono described in Sort Race by Zhang, Meng and Liang

Bug fixes

• Fix compiler error in hybrid_adapter when too many sorters of the same category are passed
• Make sure all adapted sorters can also be converted to function pointers
• Fix probe::runs: it only took increasing sequences into account and didn't behave properly with non-increasing ones (where several elements in an increasing sequence compare equivalent)
• Properly perfect-forward iterable parameters in hybrid_adapter
• Actually provide container_aware_adapter when including <cpp-sort/adapters.h>
• Apply utility::as_function to the comparison and projection functions passed to self_sort_adapter, fixing a few errors when it is used with pointers to class members

Tiny improvements

• Don't copy instances of locale in case_insensitive_less
• Actually create a minimal number of poplars in poplar_sorter, even in corner cases
• Tiny optimization in indirect_adapter
• Don't wrap adapters in sorter_facade when they don't need to, slightly reducing the template "stack traces" when there are errors
• Small changes here and there to reduce the binary size a bit

Tooling

• Set up code coverage via codecov.io (#120)
• Globally document exception guarantees for the library (#105)
• Enable ccache for clang++ with the Linux CI
• Simpler and more consistent .travis.yml where possible

1.0.0

This release is merely a point in time where the project starts being versioned. A changelog would be meaningless since there is nothing to compare it against.