[OT] n-way union

[BCS]

Hello Andrei,

> 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
> 

in sudocode

1. build a min heap out of the elements based on the first element of each 
array
2. remove the first value from the root of the heap,
3. if empty array, drop it
4. if not empty re-heap
5. goto 2 if anything left