This is Merge Sort Java Code. Please add comments on each line of codes to descr

Question

This is Merge Sort Java Code. Please add comments on each line of codes to describe what doing

public static void MergeSort( int [] A, int p, int r){
  
  
   if( p < r ) {
       int q = (int) Math.floor((p+r)/2);
       MergeSort(A,p,q);
       MergeSort(A,q + 1,r);
       Merge(A,p,q,r);
   }
  
}

public static void Merge( int [] A, int p,int q, int r){
  
   int n1 = q - p +1;
   int n2 = r - q;
  
   int [] left= new int [n1+1 ];
   int [] right = new int [n2+1 ];
  
   for(int i = 0;i<n1;i++)
   {
       left[i] = A[p+i];
   }
  
   for(int j = 0; j < n2;j++)
   {
       right[j] = A[q +j+1];
      
   }
  
   left[n1] = Integer.MAX_VALUE;
   right[n2] = Integer.MAX_VALUE;
  
   int i = 0;
   int j = 0;
  
   for(int k = p; k <= r;k++){
      
       if(left[i] <= right[j]){
           A[k] = left[i];
           i = i+1 ;
       }
      
       else {
           A[k] = right[j];
           j = j+1;
       }
   }
}

Explanation / Answer

/*
This function merges two sorted (sub)array of A, where
p is the starting index of 1st Sub-array
q is the ending index of 1st sub-array
2nd array starts from index q+1
r is the ending index of the second array

Let:
p = 1, q = 3, r = 8
first array consist of elements with index 1 2 3, and hence the length is 3 - 1 + 1 (q - p + 1)
second array consist of elements with index 4 5 6 7 8 and hence the length 8 - 3 (r - q)
*/

public static void Merge( int [] A, int p,int q, int r){
  
    int n1 = q - p +1; //length of 1st array
    int n2 = r - q;    //length of 2nd array
  
    int [] left= new int [n1+1 ];   //create auxiliary array
    int [] right = new int [n2+1 ]; //create auxiliary array
  
    for(int i = 0;i<n1;i++)   //this loops copies 1st array into array left
    {
        left[i] = A[p+i];
    }
  
    for(int j = 0; j < n2;j++)   //this loops copies 2nd array into array right
    {
        right[j] = A[q +j+1];
      
    }
  
    left[n1] = Integer.MAX_VALUE;   //last value of each auxiliary array contains the largest possible integer
    right[n2] = Integer.MAX_VALUE; //use of this element is explained later
  
    int i = 0; //i points to the 1st element of left[]
    int j = 0; //j points to the 1st element of right[]
  
    for(int k = p; k <= r;k++){ //these array copies values from two auxiliary arrays
      
        if(left[i] <= right[j]){//if ith element of left[] is less than jth element of right[]
            A[k] = left[i];   //copy the ith element of left[] to the main array A
            i = i+1 ;       // and increase i so that the same element is not cppied twice
        }
      
        else {           //if ith element of left[] is less than jth element of right[]
            A[k] = right[j];    //copy the ith element of left[] to the main array A
            j = j+1;       // and increase i so that the same element is not cppied twice
        }
   /*
   * NOTE that once i reaches the value n1 OR j reaches the value n2
   * left[n1] or right[n2] is never coppied to the main array A
   * because they contains the highest possible integer value
   * and as a result the other array elements are coppied to the main array
   * and when i becomes n1 AND j becomes N2 the for loop terminats
   * since n1 + n2 = q - p + 1 + r - q = r - p + 1
   * and the length of the for loop is also r - p + 1
   * so Integer.MAX_VALUE is never copied
   /*
    }
}

I hope this solves your issue. Don't forget to give a thumb's up if this answer helps you! Cheers!

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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