sorting with expensive compares?

[bonono at gmail.com]

gene tani wrote:
> 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
I may have made a mistaken in that hash(a) should be some function that
returns the "order" of a, rather than the built-in hash() function.