simultaneous multiple key sorting algorithm

[sclytrack]

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


Sclytrack