SortedIteratorMerge

EntryPoint.java

import static java.util.Comparator.comparingInt;

import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.stream.Stream;

public class EntryPoint {
    public static void main(String[] args) {
        List<Integer> l1 = List.of(6, 8, 19, 21, 32, 66, 67, 77, 89);
        List<Integer> l2 = List.of(1, 3, 5, 24, 33, 45, 57, 59, 89);
        List<Integer> l3 = List.of(2, 4, 9, 18, 22, 44, 46, 89, 89);
        List<Integer> all = Stream.of(l1, l2, l3).flatMap(Collection::stream).sorted().toList();

        final List<Iterator<Integer>> iterators = List.of(l1.iterator(), l2.iterator(), l3.iterator());

        Iterator<Integer> it = new SortedIteratorMerger<>(iterators);

        final long start = System.nanoTime();
        while (it.hasNext()) {
            Integer value = it.next();
            System.out.println(value);
        }
        final long end = System.nanoTime();
        System.out.println("took " + (end - start) + " nanos");

    }
}

SortedIteratorMerger.java

import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import java.util.PriorityQueue;

public class SortedIteratorMerger<T extends Comparable<T>> implements Iterator<T> {
    private final PriorityQueue<PeekingIterator<T>> queue;

    public SortedIteratorMerger(List<Iterator<T>> iterators) {
        queue = new PriorityQueue<>(iterators.size(), Comparator.comparing(PeekingIterator::peek));
        for (Iterator<T> iterator : iterators) {
            if (iterator.hasNext()) {
                queue.add(new PeekingIterator<>(iterator));
            }
        }
    }

    public boolean hasNext() {
        return !queue.isEmpty();
    }

    public T next() {
        PeekingIterator<T> iterator = queue.poll();
        T value = iterator.next();
        if (iterator.hasNext()) {
            queue.add(iterator);
        }
        return value;
    }

    private static class PeekingIterator<T extends Comparable<T>> implements Iterator<T> {
        private final Iterator<T> iterator;
        private T nextValue;

        public PeekingIterator(Iterator<T> iterator) {
            this.iterator = iterator;
            if (iterator.hasNext()) {
                nextValue = iterator.next();
            }
        }

        public boolean hasNext() {
            return nextValue != null;
        }

        public T peek() {
            return nextValue;
        }

        public T next() {
            T value = nextValue;
            if (iterator.hasNext()) {
                nextValue = iterator.next();
            } else {
                nextValue = null;
            }
            return value;
        }
    }
}