Idempotent partition around median of 5?

[Andrei Alexandrescu via Digitalmars-d]

On 02/06/2016 02:06 AM, Ivan Kazmenko wrote:
> 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.

Yah. I think stability should be solved if there's a need/application 
for it, e.g. is there a larger algorithm that would be stable if 
partition5 were stable?

> 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.

Yah, good point. I should also add that more comparisons generally mean 
more branching and more code. -- Andrei