Merged Iterator. Uses Guava

MergedIterator.java

import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.NoSuchElementException;

import com.google.common.collect.Iterators;
import com.google.common.collect.PeekingIterator;

public class MergedIterator<T> implements Iterator<T> {
    private final Comparator<? super T> comparator;
    private final PeekingIterator<T> first;
    private final PeekingIterator<T> second;

    private MergedIterator(Comparator<? super T> comparator, Iterator<T> first, Iterator<T> second) {
        this.comparator = comparator;
        this.first = Iterators.peekingIterator(first);
        this.second = Iterators.peekingIterator(second);
    }

    @SafeVarargs
    public static <T> Iterator<T> merge(Comparator<? super T> ordering, Iterator<T>... iterators) {
        return merge(ordering, iterators, 0, iterators.length);
    }

    private static <T> Iterator<T> merge(Comparator<? super T> ordering, Iterator<T>[] iterators, int offset, int length) {
        if (length == 0) {
            return Collections.emptyIterator();
        }
        if (length == 1) {
            return iterators[offset];
        }
        return new MergedIterator<>(ordering,
            merge(ordering, iterators, offset, length / 2),
            merge(ordering, iterators, offset + length / 2, length - (length / 2)));
    }

    @Override
    public boolean hasNext() {
        return first.hasNext() || second.hasNext();
    }

    @Override
    public T next() {
        if (!first.hasNext()) {
            if (!second.hasNext()) {
                throw new NoSuchElementException();
            }
            return second.next();
        }

        return !second.hasNext() || (comparator.compare(first.peek(), second.peek()) <= 0) ? first.next() : second.next();
    }
}

MergedIteratorTest

import static org.assertj.core.api.Assertions.assertThat;

import java.util.Iterator;

import org.junit.Test;

import com.google.common.collect.Iterators;
import com.google.common.collect.Lists;
import com.google.common.collect.Ordering;

public class MergedIteratorTest {
    @Test
    public void merge() {
        Iterator<Integer> stream1 = Iterators.forArray(4, 6);
        Iterator<Integer> stream3 = Iterators.forArray(1, 3, 5, 7, 9, 11);
        Iterator<Integer> stream2 = Iterators.forArray(2, 8, 10);

        Iterator<Integer> merged = MergedIterator.merge(Ordering.natural(), stream1, stream2, stream3);

        assertThat(Lists.newArrayList(merged)).hasSize(11).isSorted();
    }
}