Idempotent partition around median of 5?

[Ivan Kazmenko via Digitalmars-d]

On Saturday, 6 February 2016 at 00:59:17 UTC, Andrei Alexandrescu 
wrote:
> On 02/05/2016 06:36 AM, Ivan Kazmenko wrote:
>> Another interesting task would be to make the function stable, 
>> but I don't see how it is possible with such flat structure.
>
> Under what circumstances isn't your function unstable? -- Andrei

For example, if elements are "value | id", compared by value, 
then:
0|0, 0|1, 1|2, 0|3, 0|4
is transformed into
0|0, 0|1, 0|4, 0|3, 1|2
and 0|4 is now placed earlier than 0|3, which violates the 
stability requirement.
Things can be reordered a bit, but it seems that no possible 
order eliminates the need to remember a part of the history.

On the other hand, when we track our whole path in the decision 
tree (e.g. at the leaves of Timon Gehr's tree of ifs), we have 
all information to make the partition stable.

In any case, finding the shortest-code stable partition-of-5 
algorithm looks like a problem solvable by an automated searcher.

Regarding the speed, there are different use cases with different 
requirements, for example:

1. Primitive types (cheap swap, cheap comparison).

2. Heavy structs A (expensive swap, cheap comparison - e.g., 
compare one field of primitive type).

3. Heavy structs B (expensive swap, expensive comparison - e.g., 
call a heavy external function).

4. Heavy classes (cheap swap - pointers only, expensive 
comparison).

So there's perhaps no single best solution.