In Java Language Consider two arrays A and B, each storing n dierent integer val

Question

In Java Language

Consider two arrays A and B, each storing n dierent integer values. All values in A and B are dierent. In both arrays the values are sorted in increasing order. Write an algorithm that merges A and B and stores their values in an array C in such a way that the rst n values in C are sorted in increasing order and the last n values are sorted in decreasing order. For example, if A and B are as follows:
A

0   1   2   3    4

B

0   1   2   3     4

Then array C must be this:

0    1    2    3    4    5      6       7       8       9
You cannot use any auxiliary data structures and you must write the complete algorithm (you cannot invoke algorithms for which you do not provide pseudocode).

Compute the time complexity of your algorithm for the previous question in the worst case. Explain how you computed the time complexity and give the order of the time complexity.

Explanation / Answer

Hi, Please find my PsudoCode.

Please let me know in case of any issue.

void MergerTwoSortedArray(int[] A, int[] B, int[] C){
  
   int i,j,k;

   int n = A.length;
   i = 0;
   j = 0;

   // storing first n numbers in increasing order
   while(k < n){
       if(A[i] < B[j]){
           C[k] = A[i];
           i++;
       }
       else {
           C[k] = B[j];
           j++;
       }

       k++;
   }

   // Now Copying last n numbers in decreasing order
   int a = n-1;
   int b = n-1;

   while(a >=i && b >= j){

       if(A[a] > B[b]){
           C[k] = A[a];
           a--;
       }
       else{
           C[k] = B[b];
           b--;
       }

       k++;
   }

   // copying remaing elements from A or B if any

   while(a >= i){
       C[k] = A[a];
       a--;
       k++;
   }

   while(b >= j){
       C[k] = B[b];
       b--;
       k++;
   }
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.