Adapters vs. sorters

[Morwenn]

When I first came up with the design for adapters, I had in mine adapters that wrap a sorter and alter its behaviour such as stable_adapter or schwartz_adapter: the sorting algorithm is in the sorter proper, and the adapter wraps it and alters the behaviour somehow, but does not contain the sorting logic:

• make_stable makes a sorter stable but only the comparison logic is changed, the sorting logic isn't altered.
• counting_adapter simply wraps the comparison function to gather more information about the sorting process.
• indirect_adapter and schwartz_adapter are mere tools to trade slow copies or projections against a higher memory usage.

Most of the sorters are self-contained algorithms where their name evokes the main sorting logic used underneath and aren't configurable with other sorters.

However, some entities in the library are (or could be) halfway between a sorter and an adapter:

• verge_adapter implements a potentially cheap optimization on top of a given sorter, and can even sort the collection all by itself in some cases, but is expected to fallback to the wrapped sorter most of the time.
• split_sorter is actually is the same class of algorithms since it implements an optimization for collections with some amount of presortedness, but otherwise falls back to a sorter, and the characteristics of split_sorter actually depend on those of the underlying algorithm.
• spread_sorter uses pdq_sort as a fallback when the collection is too small, but when it is used, it generally expecting bigger collections.
• Many algorithms fall back to insertion_sort and there isn't really another algorithm that they could fallback to. It's generally part of the design of the algorithm, and not an arbitrary choice.

---

Now, this is a bit of a mess, and the design of #104 is also meant to allow passing sorters to sorters. For cpp-sort 2.0 I would like to clean that a bit and get rid of duplication (ex: verge_sorter vs. verge_adapter). There isn't a clean cut strategy, so I will probably do things as follows:

• Adapters mostly don't contain sorting logic, which means that verge_adapter will disappear and that split_adapter won't become a thing.
• Sorters for which the fallback sorting algorithm can change will be able to take it at construction time, so verge_sorter and split_sorter will gain that ability. Such sorters will default to the algorithm that makes the most sense for them (for the corresponding *_sort variable), generally the one used in as a fallback in cpp-sort 1.x.

Since cpp-sort 2.0 is expected to be a C++20 library, CTAD will make passing sorters to sorters and adapters simpler so no branding everything as adapters is more palatable, it merely becomes sorters with configuration.

[Morwenn]

An advantage of having verge_sorter and split_sorter as sorters and not as adapters is that they won't be subject to the design issues described in #134 anymore: there wasn't any obvious way to make them forward a value returned from their fallback sorter anyway, especially considering that it wasn't guaranteed that such a fallback sorter would be called when sorting an algorithm.

This might help to make a useful criterion: if it is not possible to make an adapter forward its result somehow because of its internal logic, then maybe it's better to make it a sorter.

[Morwenn]

Mutable sorters with construction time guarantees could also pave the way for the shell sort and comb sort customizations described in #44, allowing to get back to a very old issue.