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
