simultaneous multiple key sorting algorithm

[Peter Alexander]

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

Can you define "better"?

Obviously you can't beat the O(n lg n) for comparison based 
ordering. The O(n) space may be avoidable, but it doesn't seem 
like the end of the world.

Does this problem occur frequently enough in practice to justify 
having an optimised version in the standard library? Three sorts 
+ O(n) space sounds fine to me.