Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Merge K Sorted Arrays

Objec­tive: Given k sorted array, write an algo­rithm to merge Them into One sorted array.

Exam­ple :

int[][] A = new int[5][];

A[0] = new int[] { 1, 5, 8, 9 };
A[1] = new int[] { 2, 3, 7, 10 };
A[2] = new int[] { 4, 6, 11, 15 };
A[3] = new int[] { 9, 14, 16, 19 };
A[4] = new int[] { 2, 4, 6, 9 };

Output:
[1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 8, 9, 9, 9, 10, 11, 14, 15, 16, 19]

Naive Solu­tion: O(nkLognk)

  • Cre­ate an result[] of size n*k.
  • Copy all the ele­ments from k arrays into result array. This will take O(nk).
  • Sort the result[] using Merge Sort. This will take O(nkLognk) time.

Bet­ter Approach: O(nkLogk)

Merge K Sorted Arrays

Merge K Sorted Arrays

  • Cre­ate an result[] of size n*k.
  • Cre­ate Min-Heap of type HeapN­ode.( HeapN­ode– Every Node will store the data and the list no from which it belongs).
  • Now take one ele­ment from each of the K list and cre­ate HeapN­ode object and insert into min-Heap.
  • Extract the min­i­mum Node from the min-Heap, insert the data into result array.
  • The extracted node will also con­tain the list to which it belongs, insert the next ele­ment from that list into min-Heap.
  • If any point of time any list gets over, insert +∞ into min-Heap.
  • Keep repeat­ing until all the K list gets over.

Com­plete Code:


Out­put:

[1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 8, 9, 9, 9, 10, 11, 14, 15, 16, 19]

You may also like...

  • Rohit Dum­bre

    Great Code ! How­ever, I didn’t under­stand few things here.
    1. Why are you start­ing at heap loca­tion 1 instead of 0.
    2. Dur­ing the ini­tial­iza­tion you are basi­cally insert­ing the first ele­ment of every array into the heap. You will never come across ptrs[i] > n. Because you ini­tial­ized ptrs[i] to be zero.

    • tuto­ri­al­hori­zon

      1. We start with heap loca­tion 1 because ,
      For any given node at posi­tion i:
      – Its Left Child is at [2*i] if avail­able.
      – Its Right Child is at [2*i+1] if avail­able.
      So “i” can­not be 0. Read this link for more infor­ma­tion.
      http://algorithms.tutorialhorizon.com/binary-min-max-heap/

      2. ptrs[] start with 0 and goes till n-1. So when it becomes n, we will set the value as
      Integer.max so it will never become greater than n.