simultaneous multiple key sorting algorithm

[Andrei Alexandrescu]

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?


Thanks,

Andrei