simultaneous multiple key sorting algorithm

[Derek]

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?

-- 
Derek Parnell
Melbourne, Australia