In Java Let L1 and L2 be two lists of numbers sorted in incr

Let L_1 and L_2 be two lists of numbers sorted in increasing order. a. Suppose that L_1 and L_2 contain n_1 and n_2 elements respectively. Describe an O(n_1 + n_2)-time algorithm that combines the elements in L_1 and L_2 into one list where the elements are still in sorted order. b. Let us call the procedure described in part (a) as the union of the two lists. Suppose we now have k lists L[1], L[2], ..., L[k] whose elements are also in sorted order. We again want to combine all of them into a single list so that the elements are still in sorted order. Here\'s a simple procedure for doing this: First, take the union of L[1] and L[2]. Then take the union of L[3] and the output of the union of L[1] and L[2]. Then take the union of L[4] and the output of the previous step, etc. b. Write the above procedure in pseudocode. b. Assuming that L[1], ..., L[k] all have n elements, what is the running time of this procedure? Your answer should be in terms of n and k.

Solution

Please let me know in case of any issue.

void MergeKArrays(int arr[][], int k,int n)

int[] count = new int[k]; // keep index of each array which are to be processed.
int cnt = 0; // it\'s value will tell, number of arrays which are completly processed.
int min,idx=0;
  

while(cnt != k)
{
min = INT_MAX;
idx = -1;
for(int i = 0; i < k ; i++)
{
if(count[i] == n)
{
count[i] = -1;
cnt++;
}
if(count[i] != -1 && arr[i][count[i]] < min)
{
min = arr[i][count[i]];
idx = i;
}
  
}
if(cnt == k)
{
break;
}
System.out.println
cout << min << endl;
count[idx]+= 1;
}
}

It\'s O(n*k*k)

After checking front most element of each array (O(k) time) you print an element (n * k elements in total).