simultaneous multiple key sorting algorithm

[Andrei Alexandrescu]

On 1/27/12 5:27 PM, Derek wrote:
> On Sat, 28 Jan 2012 06:36:49 +1100, Andrei Alexandrescu
> <SeeWebsiteForEmail at erdani.org> wrote:
>
>> Here's a multikey sorting problem that's bothering me; I think it's
>> well researched but I can't find the right keywords.
>>
>> Say we have a collection of people with height and hair length
>> information. We want to get people who are "tall and long-haired".
>> More precisely, we want to order people by rank(p.height) +
>> rank(p.hairlength), where rank(p.k) is the function that returns the
>> rank of person p if ordered by key k.
>>
>> 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
>> array. But I think things can be done considerably better. Any ideas?
>
> Just a further clarification ...
>
> If a person is tall and has short hair, would they be included in the
> sort? In other words, are you ONLY looking for tall AND long-haired
> people or are you looking for relative ranking of tallness and hairiness?

Everybody is included in the sort: the size of the array before and 
after the sort is the same. Then, of course, the top K problem is very 
interesting too.

Andrei