More first-class support for stable_compare

[Morwenn]

stable_compare is the comparison function adapter used to make a comparison function stable and is most notably used by make_stable. Currently, unless an algorithm has a specialization for stable_adapter, using the main template will default to using make_stable if the adapted sorter isn't marked as stable. This is fine but it fails to take known facts into account: for example stable_adapter(pdq_sort) will use make_stable but will perform useless work in utility functions known to be stable (the insertion_sort variants). To make stable sorting better, I propose the following enhancements:

• Overload some internal utility algorithms known to be stable to just use the wrapped comparison function when given stable_compare.
• Give its own header to stable_compare to avoid dragging make_stable and stable_adapter everywhere.
• Actually move it to <cpp-sort/comparators/stable_compare.h> so that sorter writers can overload their own algorithms for it.
• Add dedicated tests.
• Properly document it.

[Morwenn]

Of course it's not as easy to do as expected: stable_compare is tightly coupled with association and friends, and it doesn't seem to be quite usable without embedding the projection in it, which is probably why I didn't make it public and why I don't really want to make it public as is. But I don't have a better design so far, so it probably won't end up public.

The optimizations based on stable_compare overloads currently fail and I'm not sure why. More investigation is required.

[Morwenn]

After getting back to this issue I finally realized that the root idea itself is invalid and it's time to close: yes insertion_sort is stable and doesn't need indices to sort stably, but after the partitioning step of quicksort, it doesn't need to sort stably but to restore the stable order from before the partition, so it does need the extra indices comparison and can't cheat its way out of it.

This example is just one of many, but it basically means that it's never possible to cheat and avoid the extra indices and thus that the whole premise of this issue is totally invalid and there's nothing we can do about it. It won't work for insertion sort, it won't work for other algorithm either.

The only automatic way to perform fewer comparisons in stable_compare is to take advantage of three-way comparisons when available. However adding support for those is a whole other topic, best covered by issue #145.