Question

Write merge method for mergeSort method, it takes the array of data, starting index of first half, starting index of second half and end index of second half.

please use the code below to test it

public class A4Sort{
   public static void mergeSort(int[] a, int l, int h){
      if (l >= h) return;
      int mid = (h + l) / 2;
      mergeSort(a, l, mid); 
      mergeSort(a, mid + 1, h);
      merge(a, l, mid + 1, h); 
   }
   public static void main(String[] args){
      int[] a = {3,2,7,5,1,6,4,8,9};
      System.out.println("mergeSort a: ");
      long time, nextTime;
      time = System.nanoTime();
      mergeSort(a, 0, a.length - 1);
      nextTime = System.nanoTime();
      System.out.println("\tTime used: " + (nextTime - time) + " nseconds");
      for (int i = 0; i < a.length; i++) System.out.print(a[i] + ",");
      System.out.println();
   }

}

Answer 1

`Hey,

Note: Brother if you have any queries related the answer please do comment. I would be very happy to resolve all your queries.

public class A4Sort{
public static void mergeSort(int[] a, int l, int h){
if (l >= h) return;
int mid = (h + l) / 2;
mergeSort(a, l, mid);
mergeSort(a, mid + 1, h);
merge(a, l, mid + 1, h);
}
public static void merge(int arr[], int l, int m, int r)
{
// Find sizes of two subarrays to be merged
int n1 = m - l + 1;
int n2 = r - m;
  
/* Create temp arrays */
int L[] = new int [n1];
int R[] = new int [n2];
  
/*Copy data to temp arrays*/
for (int i=0; i<n1; ++i)
L[i] = arr[l + i];
for (int j=0; j<n2; ++j)
R[j] = arr[m + 1+ j];
  
  
/* Merge the temp arrays */
  
// Initial indexes of first and second subarrays
int i = 0, j = 0;
  
// Initial index of merged subarry array
int k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
  
/* Copy remaining elements of L[] if any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
  
/* Copy remaining elements of R[] if any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
public static void main(String[] args){
int[] a = {3,2,7,5,1,6,4,8,9};
System.out.println("mergeSort a: ");
long time, nextTime;
time = System.nanoTime();
mergeSort(a, 0, a.length - 1);
nextTime = System.nanoTime();
System.out.println("\tTime used: " + (nextTime - time) + " nseconds");
for (int i = 0; i < a.length; i++) System.out.print(a[i] + ",");
System.out.println();
}

}

Kindly revert for any queries

Thanks.