Algorithms‎ > ‎Array‎ > ‎

Merge m sorted arrays

You are provided with m arrays of n length each. The arrays are initially sorted. Give the algo to get one sorted array of mn length out of these. 

if we have limited RAM, then we can use min heap.

1) take first element of each sorted array and insert into min heap(min heap size will always m).

2) extract min element and find the corresponding array(say jth array) to that min ele.

3) insert next element of jth array

4) repeat untill heap size.

time complexity: O(m*n*log(m))

extra space: O(m)