Question

Write a generic method mergeSort based on the sort program of Fig. 19.6 (the source code is given as a separate file along with this final document, and also appended at the end of this document). Test your program that prints before sorting, sorts, and prints after sorting an Integer array, a Double array, and a String array as follows:

      Integer[] dataInt = {63, 19, 65, 38, 26, 74, 27, 25, 70, 38};

      Double[] dataDouble = {102.5, 1.98, -3.12, 45.23, 4.5, -56.78, 38.24, 12.34, -105.23, 77.39};

     String[] dataString = {"zebra", "wolf", "panda", "octopus", "monkey", "fox", "elephant", "dog", "cat", "allegator"};

// Fig. 19.6: MergeSortTest.java
// Sorting an array with merge sort.
import java.security.SecureRandom;
import java.util.Arrays;

public class MergeSortTest {
   // calls recursive sortArray method to begin merge sorting
   public static void mergeSort(int[] data) {
      sortArray(data, 0, data.length - 1); // sort entire array
   }                                  

   // splits array, sorts subarrays and merges subarrays into sorted array
   private static void sortArray(int[] data, int low, int high) {
      // test base case; size of array equals 1     
      if ((high - low) >= 1) { // if not base case
         int middle1 = (low + high) / 2; // calculate middle of array
         int middle2 = middle1 + 1; // calculate next element over     

         // output split step
         System.out.printf("split:   %s%n", 
            subarrayString(data, low, high));
         System.out.printf("         %s%n", 
            subarrayString(data, low, middle1));
         System.out.printf("         %s%n%n",
            subarrayString(data, middle2, high));

         // split array in half; sort each half (recursive calls)
         sortArray(data, low, middle1); // first half of array       
         sortArray(data, middle2, high); // second half of array     

         // merge two sorted arrays after split calls return
         merge (data, low, middle1, middle2, high);             
      }                                            
   }                               
   
   // merge two sorted subarrays into one sorted subarray             
   private static void merge(int[] data, int left, int middle1, 
      int middle2, int right) {

      int leftIndex = left; // index into left subarray              
      int rightIndex = middle2; // index into right subarray         
      int combinedIndex = left; // index into temporary working array
      int[] combined = new int[data.length]; // working array        
      
      // output two subarrays before merging
      System.out.printf("merge:   %s%n", 
         subarrayString(data, left, middle1));
      System.out.printf("         %s%n", 
         subarrayString(data, middle2, right));

      // merge arrays until reaching end of either         
      while (leftIndex <= middle1 && rightIndex <= right) {
         // place smaller of two current elements into result  
         // and move to next space in arrays                   
         if (data[leftIndex] <= data[rightIndex]) {       
            combined[combinedIndex++] = data[leftIndex++]; 
         } 
         else {                                                 
            combined[combinedIndex++] = data[rightIndex++];
         } 
      } 
   
      // if left array is empty                                
      if (leftIndex == middle2) {                             
         // copy in rest of right array                        
         while (rightIndex <= right) {                        
            combined[combinedIndex++] = data[rightIndex++];
         } 
      } 
      else { // right array is empty                             
         // copy in rest of left array                         
         while (leftIndex <= middle1) {                        
            combined[combinedIndex++] = data[leftIndex++]; 
         } 
      } 

      // copy values back into original array
      for (int i = left; i <= right; i++) { 
         data[i] = combined[i];          
      } 

      // output merged array
      System.out.printf("         %s%n%n", 
         subarrayString(data, left, right));
   } 

   // method to output certain values in array
   private static String subarrayString(int[] data, int low, int high) {
      StringBuilder temporary = new StringBuilder();

      // output spaces for alignment
      for (int i = 0; i < low; i++) {
         temporary.append("   ");
      } 

      // output elements left in array
      for (int i = low; i <= high; i++) {
         temporary.append(" " + data[i]);
      } 

      return temporary.toString();
   }

   public static void main(String[] args) {
      SecureRandom generator = new SecureRandom();

      // create unordered array of 10 random ints
      int[] data = generator.ints(10, 10, 91).toArray(); 

      System.out.printf("Unsorted array: %s%n%n", Arrays.toString(data));
      mergeSort(data); // sort array
      System.out.printf("Sorted array: %s%n", Arrays.toString(data));
   } 
} 

Answer 1

Please find the answer below.
Please do comments in case of any issue. Also, don't forget to rate the question. Thank You So Much.

MergeSortTest.java

package c15;
import java.lang.reflect.Array;
import java.util.Arrays;

public class MergeSortTest<T> {
   // calls recursive sortArray method to begin merge sorting
   public static<T extends Comparable<? super T>> void mergeSort(T[] data,Class<T> clazz) {
       sortArray(data, 0, data.length - 1,clazz); // sort entire array
   }

   // splits array, sorts subarrays and merges subarrays into sorted array
   private static<T extends Comparable<? super T>> void sortArray(T[] data, int low, int high,Class<T> clazz) {
       // test base case; size of array equals 1   
       if ((high - low) >= 1) { // if not base case
           int middle1 = (low + high) / 2; // calculate middle of array
           int middle2 = middle1 + 1; // calculate next element over   

           // output split step
           System.out.printf("split: %s%n",
                   subarrayString(data, low, high,clazz));
           System.out.printf(" %s%n",
                   subarrayString(data, low, middle1,clazz));
           System.out.printf(" %s%n%n",
                   subarrayString(data, middle2, high,clazz));

           // split array in half; sort each half (recursive calls)
           sortArray(data, low, middle1,clazz); // first half of array   
           sortArray(data, middle2, high,clazz); // second half of array   

           // merge two sorted arrays after split calls return
           merge (data, low, middle1, middle2, high,clazz);   
       }
   }   

   // merge two sorted subarrays into one sorted subarray   
   private static<T extends Comparable<? super T>> void merge(T[] data, int left, int middle1,
           int middle2, int right,Class<T> clazz) {

       int leftIndex = left; // index into left subarray
       int rightIndex = middle2; // index into right subarray   
       int combinedIndex = left; // index into temporary working array
       T[] combined = (T[]) Array.newInstance(clazz, data.length);
         
       // output two subarrays before merging
       System.out.printf("merge: %s%n",
               subarrayString(data, left, middle1,clazz));
       System.out.printf(" %s%n",
               subarrayString(data, middle2, right,clazz));

       // merge arrays until reaching end of either   
       while (leftIndex <= middle1 && rightIndex <= right) {
           // place smaller of two current elements into result
           // and move to next space in arrays   
           if (data[leftIndex].compareTo(data[rightIndex])<=0) {   
               combined[combinedIndex++] = data[leftIndex++];
           }
           else {   
               combined[combinedIndex++] = data[rightIndex++];
           }
       }

       // if left array is empty
       if (leftIndex == middle2) {   
           // copy in rest of right array
           while (rightIndex <= right) {
               combined[combinedIndex++] = data[rightIndex++];
           }
       }
       else { // right array is empty   
           // copy in rest of left array   
           while (leftIndex <= middle1) {
               combined[combinedIndex++] = data[leftIndex++];
           }
       }

       // copy values back into original array
       for (int i = left; i <= right; i++) {
           data[i] = combined[i];
       }

       // output merged array
       System.out.printf(" %s%n%n",
               subarrayString(data, left, right,clazz));
   }

   // method to output certain values in array
   private static<T> String subarrayString(T[] data, int low, int high,Class<T> clazz) {
       StringBuilder temporary = new StringBuilder();

       // output spaces for alignment
       for (int i = 0; i < low; i++) {
           temporary.append(" ");
       }

       // output elements left in array
       for (int i = low; i <= high; i++) {
           temporary.append(" " + data[i]);
       }

       return temporary.toString();
   }

   public static void main(String[] args) {
       Integer[] dataInt = {63, 19, 65, 38, 26, 74, 27, 25, 70, 38};
       Double[] dataDouble = {102.5, 1.98, -3.12, 45.23, 4.5, -56.78, 38.24, 12.34, -105.23, 77.39};
       String[] dataString = {"zebra", "wolf", "panda", "octopus", "monkey", "fox", "elephant", "dog", "cat", "allegator"};
      
       System.out.printf("Unsorted array: %s%n%n", Arrays.toString(dataInt));
       mergeSort(dataInt,Integer.class); // sort array
       System.out.printf("Sorted array: %s%n", Arrays.toString(dataInt));
      
       System.out.printf("Unsorted array: %s%n%n", Arrays.toString(dataDouble));
       MergeSortTest.<Double>mergeSort(dataDouble,Double.class); // sort array
       System.out.printf("Sorted array: %s%n", Arrays.toString(dataDouble));
      
      
       System.out.printf("Unsorted array: %s%n%n", Arrays.toString(dataString));
       MergeSortTest.<String>mergeSort(dataString,String.class); // sort array
       System.out.printf("Sorted array: %s%n", Arrays.toString(dataString));
      
      
      
   }
}