simultaneous multiple key sorting algorithm

[Vladimir Panteleev]

On Friday, 27 January 2012 at 19:36:49 UTC, 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?

I don't think you can get much better than this.

Knowing the rank (for one key) for one element requires looking 
at all the other elements. Thus, knowing the rank of all elements 
isn't possible in linear time or faster.

Knowing the ranks of only one key doesn't get you much 
information regarding the final result. Even the item ranked last 
on one key can tie for first place in combination with the other.

These observations seem to impose a strict dependency on the 
order the data is calculated. I don't see any shortcuts, but I'd 
love to be proven wrong.

You may want to ask on http://cstheory.stackexchange.com/ .