Question

Recall that in MergeSort algorithm, we used a linear-time subroutine called Merge which merges two sorted lists into a single sorted list. Now suppose there are k sorted lists and there are n elements in total in these k lists. Design an efficient algorithm that merges these k sorted lists into one sorted list. The running time of your algorithm should be a function of both n and k.

Answer 1

The method strength begins with merging arrays into groups of two. After the first merge, we have k/2 arrays. Repeatedly merge arrays in groups, now we have k/4 arrays. This is similar to the merge sort. Divide k arrays into two halves including an equal number of arrays until there are two arrays in a group. This is resulted in merging the arrays in a bottom-up manner.

• Algorithm:
  1. Design a recursive function that takes k arrays and returns the output array.
  2. In the recursive function, if the value of k is 1 then return the array else if the value of k is 2 then merge the two arrays in linear time and return the array.
  3. If the value of k is greater than 2 then divide the group of k elements into two equal halves and recursively call the function, i.e 0 to k/2 array in one recursive function and k/2 to k array in a different recursive function.
  4. Print the output array.

• C++ implementation:
  #include<bits/stdc++.h>
  using namespace std;
  #define n 4

  
  void mergeArr(int a1[], int a2[], int n1,
                             int n2, int a3[])
  {
     int i = 0, j = 0, k = 0;
    
  
     while (i<n1 && j <n2)
     {
  
         if (a1[i] < a2[j])
             a3[k++] = a1[i++];
         else
             a3[k++] = a2[j++];
     }
    
    
     while (i < n1)
         a3[k++] = a1[i++];
    
  
     while (j < n2)
         a3[k++] = a2[j++];
  }

  
  void printArr(int arr[], int size)
  {
  for (int i=0; i < size; i++)
     cout << arr[i] << " ";
  }

  
  void mergeKArr(int arr[][n],int i,int j, int output[])
  {
    
     if(i==j)
     {
         for(int p=0; p < n; p++)
         output[p]=arr[i][p];
         return;
     }
    
      if(j-i==1)
     {
         mergeArr(arr[i],arr[j],n,n,output);
         return;
     }
    
    
     int out1[n*(((i+j)/2)-i+1)],out2[n*(j-((i+j)/2))];
    
  
     mergeKArr(arr,i,(i+j)/2,out1);
     mergeKArr(arr,(i+j)/2+1,j,out2);
    
    
     mergeArr(out1,out2,n*(((i+j)/2)-i+1),n*(j-((i+j)/2)),output);
    
  }

  
  
  int main()
  {
    
     int arr[][n] = {{2, 6, 12, 34},
                     {1, 9, 20, 1000},
                     {23, 34, 90, 2000}};
     int k = sizeof(arr)/sizeof(arr[0]);
     int output[n*k];
     mergeKArr(arr,0,2, output);

     cout << "Merged array is " << endl;
     printArr(output, n*k);

     return 0;
  }

Complexity Analysis:

• Time Complexity: O( n * k * log k).
  There are log k levels as in each level the k arrays are divided in half and at each level, the k arrays are traversed. So time Complexity is O( n * k ).
• Space Complexity: O( n * k * log k).
  In each level O( n*k ) space is required So Space Complexity is O( n * k * log k)