sorting with expensive compares?

[Paul Rubin]

Kent Johnson <kent at kentsjohnson.com> writes:
> > [a] -> [ (hash(a), a) ]
> 
> This won't work - elements with different hashes will sort by hash and
> elements with the same hash will still be compared which is exactly
> what the OP is trying to avoid.

ds = sorted([(hash(c), i) for i,c in enumerate(a)])
dsu = [a[i] for hc,i in ds]

Is that what you mean?  I didn't answer the OP because I couldn't
understand the original question.  The above brings together clusters
of elements with the same hash, so if the clusters are large you can
finish the sort with relatively few comparisons.