CareerCup

This solution does not have any additional memory requirements. No heap, array needed.
Space complexity = 1
Time complexity = nk or more specifically n*(k^2) where k is number of streams (small number) and n is number of elements in a stream (worst case - number of elements in the longest stream.

1. K streams; read the first element of the first non-empty stream
2. Compare it with the first element of all streams. Find the smallest. Store the pointer to the stream to which the smallest number belongs to
3. Pop out the first element from the stream to which pointer points to.
4. Keep on doing until all streams are empty.

public class MergeSortedStreamsDemo {
    static ArrayList<Integer> mergeStreams(ArrayList<ArrayList<Integer>> streams) {

        ArrayList<Integer> resultStream = new ArrayList<>();
        int streamPointer = 0;

        int numberOfStreams = streams.size();
        int emptyStreams = 0;
        int numberToBeKickedOut = Integer.MAX_VALUE;

        while (emptyStreams != numberOfStreams) {

            emptyStreams = 0;  //set empty stream to 0 everytime
            //Get the first element of first non-empty stream
            for(int i = 0; i < numberOfStreams; i++) {
                if(streams.get(i).size() != 0) {
                    numberToBeKickedOut = streams.get(i).get(0);  //Just peek the value
                    streamPointer = i;      //stream number needs to be remembered, for the pop operation later
                    break;
                } else {
                    emptyStreams += 1;
                    if(emptyStreams == numberOfStreams) return resultStream;
                }
            }
            for (int i = 0; i < numberOfStreams; i++) {
                ArrayList<Integer> stream = streams.get(i);
                if (stream.size() != 0) {
                    if (numberToBeKickedOut > stream.get(0)) {
                        numberToBeKickedOut = stream.get(0);  //peek the value
                        streamPointer = i;                    //stream number to for pop operation later
                    }
                }
            }
            resultStream.add(streams.get(streamPointer).remove(0));    //Pop the value and put it in the result stream
//            streamPointer = 0;
        }

        return resultStream;
    }

    public static void main(String[] args) {
        ArrayList<Integer> list1 = new ArrayList<Integer>();
        ArrayList<Integer> list2 = new ArrayList<Integer>();
        ArrayList<Integer> list3 = new ArrayList<Integer>();
        ArrayList<ArrayList<Integer>> inputStreams = new ArrayList<>();
        list1.add(1);
        list1.add(2);
        list1.add(3);
        list2.add(4);
        list2.add(5);
        list2.add(6);
        inputStreams.add(list1);
        inputStreams.add(list2);
        inputStreams.add(list3);
        System.out.println(mergeStreams(inputStreams));
    }
}

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);
    }

A straightforward way is to use TreeSet. Build a N elements treeset uses O(nlogn) time.
With treeset, we don't need even require the 2 streams are sorted. I'm guessing should be a much better way.

c# implementation.
Complexity: less than O(n*log n).
I use the merging part of MergeSort algorithm. (According to the task - all the arrays are sorted.)
As the complexity of the whole MergeSort algorithm is O(n*log n), so the solution is at least not worse, and even faster, due to the absence of sorting step.

using System;
using System.Collections.Generic;
using System.Threading;

namespace MergeOfSortedArrays {

    static class Program {

        private static int[] Merge( int[] arr1, int[] arr2, SortOrder sortOrder ) {

            if ( arr1 == null ) { return arr2; }
            if ( arr2 == null ) { return arr1; }

            int[] tail = null;

            if ( arr1.Length > 1 ) {
                tail = new int[arr1.Length - 1];    
            }
            
            if ( GetConditionWithSortOrder( arr1[ 0 ], arr2[ 0 ], sortOrder) ) {
                for ( int i = 0; i + 1 < arr1.Length; i++ ) {
                    tail[ i ] = arr1[ i + 1 ];
                }
                return Concat( arr1[ 0 ], Merge( tail, arr2, sortOrder) );
            }
            
            tail = null;
            if ( arr2.Length > 1 ) {
                tail = new int[arr2.Length - 1];
            }

            for ( int i = 0; i + 1 < arr2.Length; i++ ) {
                tail[i] = arr2[ i + 1 ];
            }
            return Concat( arr2[ 0 ], Merge( arr1, tail, sortOrder ) );            
        }

        private static bool GetConditionWithSortOrder( int i1, int i2, SortOrder sortOrder ) {
            return sortOrder.Equals(SortOrder.Desc) ? i1 > i2 : i1 < i2;
        }

        private static int[] Concat( int firstElm, int[] arr ) {
            
            var res = new int[ arr.Length + 1 ];
            res[ 0 ] = firstElm;

            for ( int i = 0; i < arr.Length; i++ ) {
                res[ i + 1 ] = arr[ i ];
            }
            return res;
        }

        static void Main(string[] args) {

            foreach ( var arr in GetResult() ) {
                for ( int i = 0; i < arr.Length; i++ ) {
                    Console.Write( $"{arr[i]} " );
                }
                Console.WriteLine($"{Environment.NewLine}-------------------------------");
            }
            Console.ReadLine();
        }

        private static IEnumerable<int[]> GetResult() {
                        
            var listOfArrays = new List<int[]> ();

            while ( listOfArrays.Count < 11 ) {

                Thread.Sleep( 1000 );

                var order = SortOrder.Asc;
                listOfArrays.Add( GetNewSortedArrayFromStream( order ) );
                
                int[] res = null;
                foreach ( var item in listOfArrays ) {
                    res = Merge( res, item, order );
                }

                yield return res;
            }
        }

        private static int[] GetNewSortedArrayFromStream( SortOrder order ) {

            Random rand = new Random();
            var startVal = rand.Next( 0, 101 );
            var step = rand.Next( 1, 20 );
            var length = rand.Next( 3, 10 );

            var arr = new int[ length ];
            for ( int i = 0; i < length; i++ ) {
                arr[ i ] = startVal + ( order.Equals( SortOrder.Asc ) ? i : -i ) * step;
            }
            return arr;
        }

    }

    public enum SortOrder {
        Asc,
        Desc
    }
}

If I relax stream and array keyword from the question , it translates into common problem of merging 2 sorted linked list.

// Program to merge 2 sorted list

Node Merge(Node head1 , Node head2){
if(head1 == null) return head2;
if(head2 == null) return head1;

if(head1.Data < head2.Data) {
     head1-> next = Merge(head1.Next,head2);
     return head1;
 }
else if( head1.Data > head2.Data){
     head2-> next = Merge(head1,head2->Next);
     return head2;
 }
 else {
        head2->Next = Merge(head1->Next,head2->Next);
        head1 -> Next = head2;
        return head1;
 }
}

I'd use some sort of heap with a reasonably fast merge operation that can be constructed fast from a sorted array.