simultaneous multiple key sorting algorithm

[Andrei Alexandrescu]

On 1/27/12 5:35 PM, Christof Schardt wrote:
>>>> The brute force approach would essentially compute the two ranks and
>>>> then sort by their sum. That's three sorts and at least one temporary
>
> I think, you are mixing two problem levels:
>
> Level one (theory):
> How are the two properties weighted against each other
> and can be combined to a total weight (a weight-function).

There's no weighing. The sorting order is rank(k1) + rank(k2).

> Level two (programming):
> how can this be expressed in an optimal algorithmical way,
> given D2.
>
> Your question suggests, the the (naive) sum-function is
> already the solution to level one.

This is not naive, because the quantities being summed are ranks, not 
key values.

> But I suspect, that the solution for the problem requires
> rather to find a proper weight function than a
> combinatation-algorithm.

No, I think this is a confusion.


Andrei