[OT] n-way union

[Andrei Alexandrescu]

Don wrote:
> Andrei Alexandrescu wrote:
>> I think you can't do better. Complexity is O(n) at a minimum because 
>> you need to go through each element. The heap-based algorithm has O(n 
>> log m). What you could improve on is the log m factor (m = the number 
>> of sets).
> 
> Depending on what "going through each element" means. Certainly, if you 
> need to move them, you can't beat O(n) moves, but you can definitely get 
> O(m*m) < < O(n) comparisons in the best case I described. And that would 
> also be the number of splicing operations.

Oh, I see. So yes, comparisons can be reduced. So how exactly do you 
think that can be done? By binary searching the upper bound of the head 
to find a long run of identical elements?


Andrei