Re: [Algorithms] sort and sweep / sweep and prune and just touching objects

[Jon W. <jw...@gm...>]

Pau...@sc... wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA256
>
>   
>> In a stable sort, you generally have a tie breaker, such as the "this" 
>> pointer of the value in question, in the case of a tie.
>>     
>
> Hmmm, wouldn't that mean i'd need to do the expensive value vs value test 
> anyway first?
>   

If the problem is that the same value maps to multiple indices, then I 
don't see why -- you get a stable sort by checking index (as long as the 
index relates to the value).

If the problem is that the same index maps to multiple values, then yes, 
you need to check values.

If the problem is that you have non-unique values, which map to 
non-unique indices, but you want an ordering between separate values 
with the same value/index, then using a tie-breaker is one solution.

Sincerely,

jw