[OT] n-way union

[Robert Fraser]

Andrei Alexandrescu wrote:
> This is somewhat OT but I think it's an interesting problem. Consider 
> the following data:
> 
> double[][] a =
> [
>     [ 1, 4, 7, 8 ],
>     [ 1, 7 ],
>     [ 1, 7, 8],
>     [ 4 ],
>     [ 7 ],
> ];
> 
> We want to compute an n-way union, i.e., efficiently span all elements 
> in all arrays in a, in sorted order. You can assume that each individual 
> array in a is sorted. The output of n-way union should be:
> 
> auto witness = [
>     1, 1, 1, 4, 4, 7, 7, 7, 7, 8, 8
> ];
> assert(equal(nWayUnion(a), witness[]));
> 
> The STL and std.algorithm have set_union that does that for two sets: 
> for example, set_union(a[0], a[1]) outputs [ 1, 1, 4, 7, 7, 8 ]. But 
> n-way unions poses additional challenges. What would be a fast 
> algorithm? (Imagine a could be a very large range of ranges).
> 
> Needless to say, nWayUnion is a range :o).
> 
> Finally, why would anyone care for something like this?
> 
> 
> Andrei

I'd be interested if there's some way to remove duplicates.