[OT] n-way union

[Andrei Alexandrescu]

Georg Wrede wrote:
> Andrei Alexandrescu wrote:
>> You can assume that each array is sorted.
> 
> Err, you didn't comment on my algorithm, at the end. So, either it is 
> worthless to an extent not deserving even a dismissal, or you didn't 
> read the rest of the post.

I am sorry, at the first two reads I did not understand your algorithm. 
I noticed that it is more complicated than the canonical one, and also 
it necessitates storage to hold the entire output. At the third read I 
did understand it, or at least I understood how you mean it to work. It 
has at least one bug here:

========
Sort the array of structs, and beginning with the first struct, pop from 
the pointed-to subarray as long as it contains elements equal to the 
first one. Then pop from the subarray that belongs to following struct, 
and so on, until a subbarray's first element already is larger.
========

It would fail on the data:

double[][] a =
[
     [ 1, 1, 4, 7, 8 ],
     [ 7 ],
];

You will pop all 1s and then you'll pop 7. You should be popping 4.


Andrei