Question

Complete the java code as per the comments

public class Sorting
{
   ///////////////////////////////////////////////
   // STEP 1 -- Make sorting methods generic
   ///////////////////////////////////////////////
  
   /**
   * Re-orders the contents given array using the insertion sort algorithm.
   *
   * @param data The array to be sorted.
   */
   //TODO: Make me generic to work on any kind of Comparable data!
   public static void insertionSort(int[] data)
   {
       int insert; // temporary variable to hold element to insert
      
       // loop over data.length - 1 elements
       for (int next = 0; next < data.length; next++)
       {
           insert = data[ next ]; // store value in current element
           int moveItem = next; // initialize location to place element
         
           // shift items in the sorted part of the array to make room for next element
           // making sure we don't step off the front of the array
           while (moveItem > 0 && data[ moveItem - 1 ] > insert)
           {   
               data[ moveItem ] = data[ moveItem - 1 ]; // shift element right one slot
               moveItem--;
           }
         
           data[ moveItem ] = insert; // place inserted element
       }
   }
  
   /**
   * Sorts passed data using Merge Sort by modifying the input array.
   *
   * @param data The data to be sorted.
   */
   //TODO: Make me generic to work on any kind of Comparable data!
   public static void mergeSort(int[] data)
   {
       mergeSortHelper(data, 0, data.length - 1);
   }
  
   /**
   * Recursive helper method for mergeSort.
   * @param data The data in which the sub-array is located
   * @param left Lower index of the sub-array.
   * @param right Upper index of the sub-array.
   */
   //TODO: Make me generic to work on any kind of Comparable data!
   private static void mergeSortHelper(int[] data, int left, int right)
   {
       //General Case: The sublist has at least one item in it.
       if ((right - left) >= 1)  
       {
           int middle1 = (left + right) / 2;
           int middle2 = middle1 + 1;
          
           mergeSortHelper(data, left, middle1);
           mergeSortHelper(data, middle2, right);

           merge(data, left, middle1, middle2, right);
       }
   }
  
   /**
   * Helper method for merge sort. Merges two sub-arrays into sorted order.
   *
   * @param data The data in which the sub-arrays are located
   * @param left Lower index of first sub-array.
   * @param middle1 Upper index of first sub-array.
   * @param middle2 Lower index of second sub-array.
   * @param right Upper index of second sub-array.
   */
   //TODO: Make me generic to work on any kind of Comparable data!
   private static void merge(int[] data, int left, int middle1, int middle2, int right)
   {
       int leftIndex = left;                   // Local variables for tracking left and right
       int rightIndex = middle2;               // while merging.
      
       int[] combined = new int[data.length];   // A temporary place where we can store our merged results
      
       int combinedIndex = left;       //The position we are at filling up combined
      
       // As long as both subarray pieces have data still in them,
       // we need to keep picking the next smallest from the start
       // of each and putting it into combined
       while (leftIndex <= middle1 && rightIndex <= right)
       {
           // Is the first item of the left subarray smaller?
           if (data[leftIndex] <= data[rightIndex])
           {
               combined[combinedIndex++] = data[leftIndex++];
           }
           // Or is the first item in the right one smaller?
           else
           {
               combined[combinedIndex++] = data[rightIndex++];
           }
       }

       // If the left sub-array has run out of values, we need
       // to go through emptying the remainder from the right
       if (leftIndex == middle2)
       {
           while (rightIndex <= right)
           {
               combined[combinedIndex++] = data[rightIndex++];
           }
       }
       // Otherwise, check whether the right one is empty and
       // grab any remaining values from the left sub-array
       else
       {
           while (leftIndex <= middle1)
           {
               combined[combinedIndex++] = data[leftIndex++];
           }
       }
          
       // Lastly, copy the merged array values back into the
       // original input array so it will be sorted after
       // returning from merge.
       for (int i = left; i <= right; i++)
       {
           data[i] = combined[i];
       }      
   }
  
   ///////////////////////////////////////////////////////
   // STEP 2 - Refactor Insertion Sort
   //
   //TODO: Write the helper method described below and then
   // simplify insertionSort to eliminate duplicate code
   ///////////////////////////////////////////////////////
  
   /**
   * insertionSortRange is a generic method that allows for
   * sorting a sub-range of Comparable array values using the
   * insertion sort algorithm.
   *
   * Ranges are specified with the parameters left and right,
   * which are inclusive.
   *
   * @param data The array of data to sort
   * @param left The index of the left-most position to sort
   * @param right The index of the right most position to sort
   */
   //TODO: Write the method header and body for insertionSortRange here

  
   //////////////////////////////////////////////////////
   // STEP 3 - Complete TimSort
   //////////////////////////////////////////////////////
  
   /**
   * timSort is a generic sorting method that sorts an array of Comparable
   * data using the TimSort algorithm. Make sure this method is public so
   * that we can test it.
   *
   * @param data The array of data to be sorted
   */
   //TODO: Write the method header for timSort here. Just uncomment the body, do not edit it.
   /*
   {
       timSortHelper(data, 0, data.length - 1);
   }
   */
  
  
   /**
   * timSortHelper is a generic sorting method that sorts a sub-array array of Comparable
   * data using the TimSort algorithm. This method should be public for testing purposes
   * but would normally be private.
   *
   * Ranges are specified with the parameters left and right,
   * which are inclusive.
   *
   * @param data The array of data to sort
   * @param left The index of the left-most position to sort
   * @param right The index of the right most position to sort
   */
   //TODO: Now write the header and body of the timSortHelper method as described
   // for the algorithm.
  
  
  
}

Answer 1

import java.util.*;


public class T
{
   ///////////////////////////////////////////////
   // STEP 1 -- Make sorting methods generic
   ///////////////////////////////////////////////
   
   /**
   * Re-orders the contents given array using the insertion sort algorithm.
   * 
   * @param data The array to be sorted.
   */
   //TODO: Make me generic to work on any kind of Comparable data!
   public static void insertionSort(Comparable[] data) 
   {
       Comparable insert; // temporary variable to hold element to insert
       
       // loop over data.length - 1 elements
       for (int next = 0; next < data.length; next++) 
       { 
           insert = data[ next ]; // store value in current element
           int moveItem = next; // initialize location to place element
         
           // shift items in the sorted part of the array to make room for next element
           // making sure we don't step off the front of the array
           while (moveItem > 0 && greaterThan(data[moveItem-1], insert)) 
           {   
               data[ moveItem ] = data[ moveItem - 1 ]; // shift element right one slot
               moveItem--;
           } 
         
           data[ moveItem ] = insert; // place inserted element
       }
   }
   
   private static boolean greaterThan(Comparable left, Object right)
        { return left.compareTo(right) == 1; }
        
    private static boolean lessThan(Comparable left, Object right)
        { return left.compareTo(right) == -1; }
        
    private static boolean greaterThanEqual(Comparable left, Object right)
        { return left.compareTo(right) >= 0; }
    
    private static boolean lessThanEqual(Comparable left, Object right)
        { return left.compareTo(right) <= 0; }
   
   /**
   * Sorts passed data using Merge Sort by modifying the input array. 
   * 
   * @param data The data to be sorted.
   */
   //TODO: Make me generic to work on any kind of Comparable data!
   public static void mergeSort(Comparable[] data)
   {
       mergeSortHelper(data, 0, data.length - 1);
   }
   
   /**
   * Recursive helper method for mergeSort.
   * @param data The data in which the sub-array is located
   * @param left Lower index of the sub-array.
   * @param right Upper index of the sub-array.
   */
   //TODO: Make me generic to work on any kind of Comparable data!
   private static void mergeSortHelper(Comparable[] data, int left, int right)
   {
       //General Case: The sublist has at least one item in it.
       if ((right - left) >= 1)   
       {
           int middle1 = (left + right) / 2;
           int middle2 = middle1 + 1;
           
           mergeSortHelper(data, left, middle1);
           mergeSortHelper(data, middle2, right);

           merge(data, left, middle1, middle2, right);
       }
   }
   
   /**
   * Helper method for merge sort. Merges two sub-arrays into sorted order.
   * 
   * @param data The data in which the sub-arrays are located
   * @param left Lower index of first sub-array.
   * @param middle1 Upper index of first sub-array.
   * @param middle2 Lower index of second sub-array.
   * @param right Upper index of second sub-array.
   */
   //TODO: Make me generic to work on any kind of Comparable data!
   private static void merge(Comparable[] data, int left, int middle1, int middle2, int right)
   {
       int leftIndex = left;                   // Local variables for tracking left and right
       int rightIndex = middle2;               // while merging.
       
       Comparable[] combined = new Comparable[data.length];   // A temporary place where we can store our merged results 
       
       int combinedIndex = left;       //The position we are at filling up combined
       
       // As long as both subarray pieces have data still in them, 
       // we need to keep picking the next smallest from the start
       // of each and putting it into combined
       while (leftIndex <= middle1 && rightIndex <= right)
       {
           // Is the first item of the left subarray smaller?
           if (lessThanEqual(data[leftIndex], data[rightIndex]))
           {
               combined[combinedIndex++] = data[leftIndex++];
           }
           // Or is the first item in the right one smaller?
           else 
           {
               combined[combinedIndex++] = data[rightIndex++];
           }
       }

       // If the left sub-array has run out of values, we need
       // to go through emptying the remainder from the right
       if (leftIndex == middle2)
       {
           while (rightIndex <= right)
           {
               combined[combinedIndex++] = data[rightIndex++];
           }
       }
       // Otherwise, check whether the right one is empty and 
       // grab any remaining values from the left sub-array
       else
       {
           while (leftIndex <= middle1)
           {
               combined[combinedIndex++] = data[leftIndex++];
           }
       }
           
       // Lastly, copy the merged array values back into the 
       // original input array so it will be sorted after
       // returning from merge.
       for (int i = left; i <= right; i++)
       {
           data[i] = combined[i];
       }       
   }
   
   ///////////////////////////////////////////////////////
   // STEP 2 - Refactor Insertion Sort
   //
   //TODO: Write the helper method described below and then 
   // simplify insertionSort to eliminate duplicate code
   ///////////////////////////////////////////////////////
   
   /**
   * insertionSortRange is a generic method that allows for
   * sorting a sub-range of Comparable array values using the 
   * insertion sort algorithm. 
   * 
   * Ranges are specified with the parameters left and right, 
   * which are inclusive.
   * 
   * @param data The array of data to sort
   * @param left The index of the left-most position to sort
   * @param right The index of the right most position to sort
   */
   //TODO: Write the method header and body for insertionSortRange here
    public static void insertionSortRange(Comparable[] data, int left, int right) 
    { 
        for (int i = left; i <= right; i++)  
        { 
            Comparable temp = data[i]; 
            int j = i - 1; 
            while (j >= left && lessThan(data[j] , temp))  
            { 
                data[j + 1] = data[j]; 
                j--; 
            } 
            data[j + 1] = temp; 
        } 
    } 

   
   //////////////////////////////////////////////////////
   // STEP 3 - Complete TimSort
   //////////////////////////////////////////////////////
   
   /**
   * timSort is a generic sorting method that sorts an array of Comparable
   * data using the TimSort algorithm. Make sure this method is public so
   * that we can test it.
   * 
   * @param data The array of data to be sorted
   */
   //TODO: Write the method header for timSort here. Just uncomment the body, do not edit it.
   
   
      // public static void timSortHelper(T[] data, 0, data.length - 1);
   
  
   
   
   /**
   * timSortHelper is a generic sorting method that sorts a sub-array array of Comparable
   * data using the TimSort algorithm. This method should be public for testing purposes
   * but would normally be private.
   * 
   * Ranges are specified with the parameters left and right, 
   * which are inclusive.
   * 
   * @param data The array of data to sort
   * @param left The index of the left-most position to sort
   * @param right The index of the right most position to sort
   */
   //TODO: Now write the header and body of the timSortHelper method as described
   // for the algorithm.
   
        static int MIN_MERGE = 32; 
  
    public static int minRunLength(int n) 
    { 
        assert n >= 0; 
        
        // Becomes 1 if any 1 bits are shifted off 
        int r = 0; 
        while (n >= MIN_MERGE)  
        { 
            r |= (n & 1); 
            n >>= 1; 
        } 
        return n + r; 
    } 
    public static void timSortHelper(Comparable[] data, int left, int right) 
    { 
         int minRun = minRunLength(MIN_MERGE); 
         int z = right-left+1;
        
        // Sort individual subarrays of size RUN 
        for (int i = 0; i < z; i += minRun) 
        { 
            insertionSortRange(data, i, 
                          Math.min((i + 31), (z - 1))); 
        } 
  
        // Start merging from size  
        // RUN (or 32). It will 
        // merge to form size 64,  
        // then 128, 256 and so on 
        // .... 
        for (int size = minRun; size < z; size = 2 * size)  
        { 
  
            // Pick starting point  
            // of left sub array. We 
            // are going to merge  
            // arr[l..l+size-1] 
            // and arr[l+size, l+2*size-1] 
            // After every merge, we  
            // increase l by 2*size 
            for (int l = 0; l < z;  
                                 l += 2 * size)  
            { 
  
                // Find ending point of left sub array 
                // mid+1 is starting point of right sub 
                // array 
                int mid = l + size - 1; 
                int r = Math.min((l + 2 * size - 1), 
                                     (z - 1)); 
  
                // Merge sub array arr[l.....mid] & 
                // arr[mid+1....r] 
                merge(data, l, mid,mid+1, r); 
            } 
        } 
    } 
    
   
}