simultaneous multiple key sorting algorithm

[Andrei Alexandrescu]

On 1/27/12 3:07 PM, sclytrack wrote:
> On 01/27/2012 08:36 PM, Andrei Alexandrescu 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?
>>
>>
>> Thanks,
>>
>> Andrei
>
>
> http://en.wikipedia.org/wiki/K-d_tree

Thanks. I think k-d trees are good for general operations (insertion, 
deletion, and nearest neighbor query) whereas here we're interested in 
sorting.

Andrei