Question

Given an active stream of sorted arrays, how would you merge them efficiently?
C or Java code would be helpful?

Answer 1

Use min heap to hold M values from M sorted arrays, O(N*log M), N total number of elements

static class Row<T> {
        Iterator<T> aRow;
        T currentValue;

        public Row(Iterator<T> aRow) {
            this.aRow = aRow;
            // currentValue is undefined
        }

        T getV() {return currentValue ;}

        boolean advance() {
            if (aRow.hasNext()) {
                currentValue = aRow.next();
                return true;
            } else {
                return false;
            }
        }

        @Override
        public String toString() {
            return  currentValue + ":" + aRow.hasNext();

        }
    }
    @SafeVarargs
    static <T extends Comparable<T>> void merge(Consumer<T> downStream,
                                                Collection<T> ... sources) {

        PriorityQueue<Row<T>> heap = new PriorityQueue<>(sources.length,
                Comparator.comparing(Row::getV));

        for (Collection<T> it : sources) {

            Row<T> row = new Row<>(it.iterator());
            // row has any data?
            if (row.advance()) {
                heap.add(row);
            }
        }

        while(! heap.isEmpty()) {
            Row<T> row = heap.remove();
            downStream.accept(row.getV());

            // row has more data ?
            if (row.advance()) {
                heap.add(row);
            }
        }
    }

    public static void main(String[] args) {

        List<Integer> l1 = Arrays.asList(1,3, 6, 10);
        List<Integer> l2 = Arrays.asList(3,3, 10, 20);
        List<Integer> l3 = Arrays.asList(1,1, 3);
        List<Integer> l4 = Collections.emptyList();

        merge(System.out::println, l1, l2, l3, l4);
    }