sorting with expensive compares?

[gene tani]

bonono at gmail.com wrote:
> Dan Stromberg wrote:
> > Hi folks.
> >
> > Python appears to have a good sort method, but when sorting array elements
> > that are very large, and hence have very expensive compares, is there some
> > sort of already-available sort function that will merge like elements into
> > a chain, so that they won't have to be recompared as many times?
> >
> > Thanks!
> Sounds like DSU time.
>
> [a] -> [ (hash(a), a) ]

Aha!  OR: take a log of the array, e.g. log base 10 or some other
monotonic transform and permutation order indexes
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/306862