Question

Modify the MergeSort program given to support searching subarrays.

Program is listed below in Java.

public class Merge

{

public static void sort(Comparable[] a)

}

Comparable[] aux = new Comparable[a.length];

sort(a, aux, 0, a.length);

}

private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi)

{ //Sort a[lo, hi)

if (hi - lo <= 1) return;

int mid = lo (hi + lo) / 2;

sort( a, aux, lo, mid);

sort(a, aux, mid, hi);

int i = lo, j = mid;

for (int k = lo; k < hi; k++)

if (i == mid) aux[k] = a[j++];

else if (j == hi) aux[k] = a[i++];

else if (a[j].compareTo(a[i]) < 0) aux[k] = a[j++];

else aux[k] = a[i++];

for (int k = lo; k < hi; k++)

a[k] = aux[k];

}

public static void main(String[] args)

{ }

}

Note: The user would give an unsorted list of words as command-line arguments along with the starting and ending index of the subarray that should be sorted. The program should print out a list where the strings between the given indexes are sorted alphabetically.

• Sample runs would be as follows.

>java MergeSort 2 4 toy apply sand bay cat dog fish

toy apply bay cat sand dog fish

>java MergeSort 0 3 was had him and you his the but

and had him was you his the but

Answer 1

//Having Any query Please ask in comment Section

class Merge {

  
   //Merging
   void merge(String arr[], int l, int m, int r) {

       int n1 = m - l + 1;
       int n2 = r - m;

       String L[] = new String[n1];
       String R[] = new String[n2];

       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];

       int i = 0, j = 0;

       int k = l;
       while (i < n1 && j < n2) {
           if (stringCompare(L[i], R[j]) < 0) {
               arr[k] = L[i];
               i++;
           } else {
               arr[k] = R[j];
               j++;
           }
           k++;
       }

       while (i < n1) {
           arr[k] = L[i];
           i++;
           k++;
       }

       while (j < n2) {
           arr[k] = R[j];
           j++;
           k++;
       }
   }

  
   //Sorting
   void sort(String arr[], int l, int r) {
       if (l < r) {
           // Find the middle point
           int m = (l + r) / 2;

           // Sort first and second halves
           sort(arr, l, m);
           sort(arr, m + 1, r);

           // Merge the sorted halves
           merge(arr, l, m, r);
       }
   }

  
   //Comparison
   public static int stringCompare(String str1, String str2) {

       int l1 = str1.length();
       int l2 = str2.length();
       int lmin = Math.min(l1, l2);

       for (int i = 0; i < lmin; i++) {
           int str1_ch = (int) str1.charAt(i);
           int str2_ch = (int) str2.charAt(i);

           if (str1_ch != str2_ch) {
               return str1_ch - str2_ch;
           }
       }
      
       if (l1 != l2) {
           return l1 - l2;
       }

       else {
           return 0;
       }
   }

   public static void main(String[] args) {
       int start = Integer.parseInt(args[0]);            //Separating start point
       int end = Integer.parseInt(args[1]);        //Separating End point

       String[] a = new String[args.length-2];           //Separating String Values
      
      
       //Subarray For required Sort String
       String subarray[] = new String[(end - start)+1];
       int j=0;
       for(int i=0;i<a.length;i++) {
           a[i] = args[i+2];
           if(i>=start && i<=end) {
               subarray[j] = a[i];
               j++;
           }
       }
      
      
      
      
       //Sorting
       Merge merge = new Merge();
       merge.sort(subarray, 0, subarray.length-1);
      
      
       //Combining Sort array with Remaining Values
      
       String finalString = "";
       int sub=0;
       for (int i = 0; i < a.length; i++) {
           if(i>=start && i<=end) {
               finalString+=" "+subarray[sub];
               sub++;
           }else {
               finalString+=" "+a[i];
              
           }
       }
       System.out.println(finalString.trim());
      
   }
}