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.
