sorting with expensive compares?

[Kent Johnson]

bonono at gmail.com wrote:
> Dan Stromberg wrote:
>>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?
> 
> Sounds like DSU time.
> 
> [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.

If there is some function of the arrays which sorts in the same order as 
the natural comparison then that function can be used as a sort key.
sort(arrayList, key=some_proxy_function)

Kent