When is an unstable sort stable?

[Morwenn]

We can consider that an unstable sorting algorithm is stable as long as the stability isn't actually observable. For example, the lack of stability of a quicksort shouldn't be observable if the sort is performed on a C array of integers with std::less<>. Having a stable sorting algorithm fall back to a faster unstable algorithm when the stability can't be noticed could be interesting in generic code, to benefit from the speed of unstable sorting algorithms when possible.

We could introduce an unstable_adapter in the library, which takes two sorters: a stable one, and an unstable one, using the stable adapter most of the time, and falling back to the unstable one when it can statically infer that the lack of stability isn't observable.

As far as I can tell, we need guarantees for four kinds of components to statically infer that the stability isn't observable:

• A guarantee for the type of data to sort
• A guarantee for the collection (for the iterators)
• A guarantee for the comparison function
• A guarantee for the projection function

Without giving it any seconds thoughts, the following guarantees should hold:

• Stability isn't observable for integral or pointers types
• Stability isn't observable when using a total order
• Stability isn't influenced by std::less<> and std::greater<>
• Stability isn't influenced by utility::identity
• Stability isn't influenced by standard collections

Now I need to find more formal stuff to make sure that these guarantees hold, and to find a scalable way to give this information to the sorter. We could have traits, but how would they be organized? Would they take the whole information (type to sort + collection + comparison + projection)? Would there be more individual traits to tell which elements might influence the stability?

Questions, questions and more questions. There is probably a way to make that work, but it needs some more thought.