Is there any implementation of a MergeIterator?

Question

Does any of the existing collection libraries (guava, commons-collection) provide a MergeIterator that's constructed with:

MergeIterator(Iterator<Comparable> iters...)

and then (assuming the source iterators are sorted) advances through the iterators in parallel and returns the elements in order?

[1,3,5] + [2,8] => [1,2,3,5,8]

This would be a fun class to write, but I wouldn't want to reinvent the wheel.

Answer 1

Iterators.mergeSorted in Guava is such a thing.

Answer 2

You can use the CollatingIterator of commons-collections:

 List<Integer> list1 = Arrays.asList(1, 3, 5);
 List<Integer> list2 = Arrays.asList(2, 8);

 Iterator<Integer> merged =
    IteratorUtils.collatedIterator(ComparatorUtils.NATURAL_COMPARATOR,
                                   list1.iterator(), list2.iterator());

 System.out.println(IteratorUtils.toList(merged));

This will print the following:

 [1, 2, 3, 5, 8]