[OT] n-way union

[Don]

Andrei Alexandrescu wrote:
> 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?

That was my original thought, but it's easy to come up with cases that 
would perform really badly -- so that you do a binary search for every 
two elements.
Which was why I suggested repeated doubling of the stride distance, I 
think you can prove that's never worse than a linear search of every 
element.
Although, if it was worth doing, I'd imagine that implementations of STL 
set_union would already be doing it.

Anyway, it's a really interesting problem.