Merge k sorted arrays into a single sorted array
  • mergesort
  • sorting
  • sortedarray
  • timecomplexity
  • array
  • Posted: 7 years ago
  • Updated: 6 years ago
  • Edit
  • answers (1)
  • views (11435)
  • Comments (2)

Suppose you are given k sorted arrays each of length n . Combine the arrays into a single sorted array. What is the time complexity of your algorithm?

For the solution of "Min heap". Could anyone please provide a simple Java code? - posted 5 years ago @hmhs.hoseini

A minor correction: I think time complexity will be O(nk logk), since total number of elements in k sorted arrays is 'nk'. - posted 5 years ago @hmhs.hoseini

Posted Answers

We can construct the single sorted array in the following way.

  • Make a Min heap from the first element of each k sorted array. On heapifying pop the head element and put it in the first position of the resultant array of size (\( k \times n \)).
  • Take the next element from the array (among the k sorted array) where the head of the heap came from. Insert it into the Min heap. Heapify it and pop the head to the next position of the resultant array.
  • Repeat until all the elements of the k arrays are consumed and kept in the proper position in the resultant array.

Time complexity calculation :-
Number of elements in the heap = k
Time to heapify = \( O(logk) \)
No of times this heapify process repeats = Total number of elements in k sorted arrays = n
Therefore, overall time complexity of the algorithm = \( O(nlogk) \).

You need to Sign In to post your solution.