Question

Using Merge Sort: (In Java) (Please screenshot or copy your output file in the answer)

In this project, we combine the concepts of Recursion and Merge Sorting.

Please note that the focus of this project is on Merging and don't forget the following constraint:

Programming Steps:

1) Create a class called Art that implements Comparable interface.

2) Read part of the file and use Merge Sort to sort the array of Art and then write them to a file.

3) Read some more records from the file, sort them, and merge them with the sorted file on the disk.

4) Repeat the above step until it is all done.

5) Sort Artist ID first and then Art ID.

6) Sort 30 Art IDs at a time. FIrst 30, then other 30, then other 30 and so on.

7) Create temporory files to store the sorted records in.

8) After sorting all Art IDs, merge them and write to output file "p6Out.txt"

Additional Specs and Requirements:

1. Your RAM can only holds 30 records at most at any time;

2. Read the files into arrays, 30 records at a time.

3. Sort them and then write to a temporary output file.

4. So, with 116 input Art records you should have 4 temporary sorted files.

5.  You then merge two files into one, so you will then create more temp files.

6. Eventually you will have two temp files left and you merge these two into the file output file.

7. Keep all the temperorary files and their output.

Read the programming steps for guidance.

File specifications:

a) The input file that you are going to use is the tab-delimited text file "p1arts.txt".

b) the output file that you are going to produce using File I/O is also the tabdelimited text file called "p6Out.txt" which is sorted ascendingly on artistID and then artID both.

Example output follows:

(sample output)

ArtistID ArtID Title Appraised Value

1   1038   Spring Flowers   800
1   1050   Cattle Ranch   10000
1   1103   Trail End   8000
2   1042   Coffee on the Trail   7544
3   1013   Superstitions   78000
3   1021   Bead Wall   14000
3   1034   Beaver Pole Jumble   28000
3   1063   Asleep in the Garden   110000
4   1070   Beginnings   27500
5   1036   Blackhawk   25500
6   1017   Brittlecone   1300
6   1053   Blue Eyed Indian   40000
6   1056   Cavalry Is Coming   1900
6   1075   Western Boots and Spurs   6000
6   1077   Bull Riding   5200
7   1049   Buttercup with Red Lip   400
8   1018   Mountain Scene   2500
9   1055   Starlit Evening   9500
10   1096   Ceremonial Sticks   15000
11   1090   Off the Grid   8000
12   1003   Spring Flowers   2400
13   1081   Coming Under Fire   650
14   1039   Treachery   20000
14   1102   Crying Hats   10000
15   1073   Dancing in the Light   4000
16   1052   American Rodeo   3500
17   1059   Dwelling   16000
18   1005   The Hang   8000
19   1011   Eve   975
20   1099   Watch That Rattler   900
21   1037   Floating World   2350
22   1109   Friends   16000
23   1084   Crossing the Platt River   2200
24   1072   Funnel   4500
25   1115   Starry Night   8500
26   1008   End of the Path   1900
27   1112   Dark Canyon   8000
28   1009   Amen   3000
28   1030   Ash Bench   13000
28   1043   Creosote Bushes   18000
28   1078   Chuckwagon   32000
29   1041   Night Version   3800
29   1082   Spring Flowers   20000
30   1116   Apache Warrior   23000
31   1029   Horseshoe Falls   15000
32   1006   House Remembered   700
33   1046   Immediate Gratification   1500
34   1031   Inside/Out   3500
35   1107   Striking It Rich   1750
36   1051   Night Version   7000
37   1088   Lessons   3700
38   1045   Leaf Patterns   2100
38   1100   Hungry Cowboys   750
39   1094   Life Is Sweet   25000
40   1106   Horse Corral   12500
41   1062   Cowboy and Saddle   18000
42   1032   Rising Sun   2000
42   1060   Story Sticks   650
43   1044   Mexican Fiesta   14000
44   1047   Medicine Man   2500
45   1014   Plenty   500
46   1015   Punch   10000
47   1023   Shooting the Rapids   1300
47   1027   Mountain Climber   4700
47   1035   Nature/Nurture   1300
47   1040   Night on the Praire   1300
47   1065   Moonlite   1300
47   1092   Dressing Up   1300
48   1024   Spirit and Nature   592
49   1067   Owl in Flight   7000
50   1001   Red Rock Mountain   18000
50   1028   Tired Cowboy   4700
50   1054   Snake Charmer   4500
50   1068   Moonlight   9750
50   1069   Renaissance   5500
50   1113   Shadow House   5500
50   1114   Storytelling at the Campfire   18000
51   1064   Spirit Columns   7000
52   1002   Offerings   10000
53   1089   Life Lessons   4125
54   1091   Stone Palette   11500
55   1074   Storm on the Rise   8000
56   1098   Sweet Project   592
57   1048   Comfy Chair   800
58   1101   The Red Door   10000
59   1080   The Dust Behind   18000
60   1058   The Gathering   250
61   1019   The White Heart   9300
61   1095   The Spirit   20000
62   1079   Carrying the Mail   8000
62   1093   Antelopes   12500
62   1110   Three Sisters   6500
63   1085   Traces   20000
64   1004   Seeking Shelter   52000
64   1083   Untitled   2500
65   1016   Untitled   6000
66   1026   Untitled (couple)   4000
66   1057   Untitled   4500
67   1086   Untitled (desert landscape)   18000
68   1025   Profile of a Woman   625
69   1022   The Cowboy   4200
70   1104   Untitled   1800
71   1010   Untitled (land with adobe)   800
72   1111   Untitled (man and crucifix)   3200
73   1020   Untitled (Man holding coat)   3000
74   1012   Man on Horseback   8000
75   1097   Untitled (Sea)   2800
76   1066   Untitled (still life)   19500
77   1033   Untitled (Woman abstract)   2500
77   1108   Untitled Mural   400
78   1061   Untitled Mural   3520
79   1071   Ride the Rapids   300
79   1076   Ride the Bronco   1500
80   1105   Meteor Show   10000
81   1087   Three Woman   20000
82   1007   Homage to the Ancestors   1200

p1arts.txt:

1001    Red Rock Mountain       50      18000
1002    Offerings       52      10000
1003    Spring Flowers  12      2400
1004    Seeking Shelter 64      52000
1005    The Hang        18      8000
1006    House Remembered        32      700
1007    Homage to the Ancestors 82      1200
1008    End of the Path 26      1900
1009    Amen    28      3000
1010    Untitled (land with adobe)      71      800
1011    Eve     19      975
1012    Man on Horseback        74      8000
1013    Superstitions   3       78000
1014    Plenty  45      500
1015    Punch   46      10000
1016    Untitled        65      6000
1017    Brittlecone     6       1300
1018    Mountain Scene  8       2500
1019    The White Heart 61      9300
1020    Untitled (Man holding coat)     73      3000
1021    Bead Wall       3       14000
1022    The Cowboy      69      4200
1023    Shooting the Rapids     47      1300
1024    Spirit and Nature       48      592
1025    Profile of a Woman      68      625
1026    Untitled (couple)       66      4000
1027    Mountain Climber        47      4700
1028    Tired Cowboy    50      4700
1029    Horseshoe Falls 31      15000
1030    Ash Bench       28      13000
1031    Inside/Out      34      3500
1032    Rising Sun      42      2000
1033    Untitled (Woman abstract)       77      2500
1034    Beaver Pole Jumble      3       28000
1035    Nature/Nurture  47      1300
1036    Blackhawk       5       25500
1037    Floating World  21      2350
1038    Spring Flowers  1       800
1039    Treachery       14      20000
1040    Night on the Praire     47      1300
1041    Night Version   29      3800
1042    Coffee on the Trail     2       7544
1043    Creosote Bushes 28      18000
1044    Mexican Fiesta  43      14000
1045    Leaf Patterns   38      2100
1046    Immediate Gratification 33      1500
1047    Medicine Man    44      2500
1048    Comfy Chair     57      800
1049    Buttercup with Red Lip  7       400
1050    Cattle Ranch    1       10000
1051    Night Version   36      7000
1052    American Rodeo  16      3500
1053    Blue Eyed Indian        6       40000
1054    Snake Charmer   50      4500
1055    Starlit Evening 9       9500
1056    Cavalry Is Coming       6       1900
1057    Untitled        66      4500
1058    The Gathering   60      250
1059    Dwelling        17      16000
1060    Story Sticks    42      650
1061    Untitled Mural  78      3520
1062    Cowboy and Saddle       41      18000
1063    Asleep in the Garden    3       110000
1064    Spirit Columns  51      7000
1065    Moonlite        47      1300
1066    Untitled (still life)   76      19500
1067    Owl in Flight   49      7000
1068    Moonlight       50      9750
1069    Renaissance     50      5500
1070    Beginnings      4       27500
1071    Ride the Rapids 79      300
1072    Funnel  24      4500
1073    Dancing in the Light    15      4000
1074    Storm on the Rise       55      8000
1075    Western Boots and Spurs 6       6000
1076    Ride the Bronco 79      1500
1077    Bull Riding     6       5200
1078    Chuckwagon      28      32000
1079    Carrying the Mail       62      8000
1080    The Dust Behind 59      18000
1081    Coming Under Fire       13      650
1082    Spring Flowers  29      20000
1083    Untitled        64      2500
1084    Crossing the Platt River        23      2200
1085    Traces  63      20000
1086    Untitled (desert landscape)     67      18000
1087    Three Woman     81      20000
1088    Lessons 37      3700
1089    Life Lessons    53      4125
1090    Off the Grid    11      8000
1091    Stone Palette   54      11500
1092    Dressing Up     47      1300
1093    Antelopes       62      12500
1094    Life Is Sweet   39      25000
1095    The Spirit      61      20000
1096    Ceremonial Sticks       10      15000
1097    Untitled (Sea)  75      2800
1098    Sweet Project   56      592
1099    Watch That Rattler      20      900
1100    Hungry Cowboys  38      750
1101    The Red Door    58      10000
1102    Crying Hats     14      10000
1103    Trail End       1       8000
1104    Untitled        70      1800
1105    Meteor Show     80      10000
1106    Horse Corral    40      12500
1107    Striking It Rich        35      1750
1108    Untitled Mural  77      400
1109    Friends 22      16000
1110    Three Sisters   62      6500
1111    Untitled (man and crucifix)     72      3200
1112    Dark Canyon     27      8000
1113    Shadow House    50      5500
1114    Storytelling at the Campfire    50      18000
1115    Starry Night    25      8500
1116    Apache Warrior  30      23000

I am providing the sample programs that you might need:

Name.java:

/**
   A mutable class that represents a person's name.
   @author Frank M. Carrano
   @author Timothy M. Henry
   @version 4.0
*/
public class Name implements Comparable
{
        private String first; // First name
        private String last;  // Last name

        public Name()
        {
                this("", "");
        } // end default constructor

        public Name(String firstName, String lastName)
        {
                first = firstName;
                last = lastName;
        } // end constructor

        public void setName(String firstName, String lastName)
        {
                setFirst(firstName);
                setLast(lastName);
        } // end setName

        public String getName()
        {
                return toString();
        } // end getName

        public void setFirst(String firstName)
        {
                first = firstName; 
        } // end setFirst

        public String getFirst()
        {
                return first;
        } // end getFirst

        public void setLast(String lastName)
        {
                last = lastName;
        } // end setLast

        public String getLast()
        {
                return last;
        } // end getLast

        public void giveLastNameTo(Name aName)
        {
                aName.setLast(last);
        } // end giveLastNameTo

        public String toString()
        {
                return first + " " + last;
        } // end toString
   
   public int compareTo(Name other)
   {
      int result = last.compareTo(other.last);
      
      // If last names are equal, check first names
      if (result == 0)
         result = first.compareTo(other.first);
         
      return result;
   } // end compareTo
} // end Name

Artist.java:

/**
   A mutable class that represents a person's name.
   @author Frank M. Carrano
   @author Timothy M. Henry
   @version 4.0
*/
public class Artist implements Comparable, java.io.Serializable
{
        private String first; // First name
        private String last;  // Last name

        public Artist()
        {
                this("", "");
        } // end default constructor

        public Artist(String firstName, String lastName)
        {
                first = firstName;
                last = lastName;
        } // end constructor

        public void setName(String firstName, String lastName)
        {
                setFirst(firstName);
                setLast(lastName);
        } // end setName

        public String getName()
        {
                return toString();
        } // end getName

        public void setFirst(String firstName)
        {
                first = firstName;
        } // end setFirst

        public String getFirst()
        {
                return first;
        } // end getFirst

        public void setLast(String lastName)
        {
                last = lastName;
        } // end setLast

        public String getLast()
        {
                return last;
        } // end getLast

        public void giveLastNameTo(Name aName)
        {
                aName.setLast(last);
        } // end giveLastNameTo

        public String toString()
        {
                return first + " " + last;
        } // end toString

   public int compareTo(Artist other)
   {
      int result = last.compareTo(other.last);

      // If last names are equal, check first names
      if (result == 0)
         result = first.compareTo(other.first);

      return result;
   } // end compareTo
} // end Name

MergeSort.java:

// Fig. 19.10: MergeSort.java
// Class that creates an array filled with random integers.  
// Provides a method to sort the array with merge sort.
import java.util.Random;

public class MergeSort
{
   private int[] data; // array of values
   private static final Random generator = new Random();

   // create array of given size and fill with random integers
   public MergeSort( int size )
   {
      data = new int[ size ]; // create space for array

      // fill array with random ints in range 10-99
      for ( int i = 0; i < size; i++ )
         data[ i ] = 10 + generator.nextInt( 90 );
   } // end MergeSort constructor
   
   // calls recursive split method to begin merge sorting
   public void sort()
   {
      sortArray( 0, data.length - 1 ); // split entire array
   } // end method sort

   // splits array, sorts subarrays and merges subarrays into sorted array
   private void sortArray( 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.println( "split:   " + subarray( low, high ) );
         System.out.println( "         " + subarray( low, middle1 ) );
         System.out.println( "         " + subarray( middle2, high ) );
         System.out.println();

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

         // merge two sorted arrays after split calls return
         merge ( low, middle1, middle2, high );
      } // end if
   } // end method sortArray
   
   // merge two sorted subarrays into one sorted subarray
   private void merge( 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.println( "merge:   " + subarray( left, middle1 ) );
      System.out.println( "         " + subarray( 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++ ];
      } // end while
   
      // 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.println( "         " + subarray( left, right ) );
      System.out.println();
   } // end method merge

   // method to output certain values in array
   public String subarray( 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();
   } // end method subarray

   // method to output values in array
   public String toString()
   {
      return subarray( 0, data.length - 1 );
   } // end method toString 
} // end class MergeSort

ArraySorter.java:

/**
   A class of static, recursive methods for sorting an array of
   Comparable objects from smallest to largest.
   
   @author Frank M. Carrano
   @author Timothy M. Henry
   @version 4.0
*/
public class ArraySorter
{
        public static final int MIN_SIZE = 5; // For quick sort

// SELECTION SORT

   /** Sorts the first n objects in an array into ascending order.
       @param a  An array of Comparable objects.
       @param n  An integer > 0. */
        public static >
               void selectionSort(T[] a, int n)
        {
           selectionSort(a, 0, n - 1); // invoke recursive method
        } // end selectionSort

        public static > 
               void selectionSort(T[] a, int first, int last)
        {
                if (first < last)
                {  // Place the smallest value at beginning of array:
                        int indexOfNextSmallest = getIndexOfSmallest(a, first, last);
                        swap(a, first, indexOfNextSmallest);
                        selectionSort(a, first + 1, last);
                } // end if
        } // end selectionSort

   // Returns the index of the smallest value in a portion of an array.
   private static >
           int getIndexOfSmallest(T[] a, int first, int last)
   {
      T min = a[first];
      int indexOfMin = first;
      for (int index = first + 1; index <= last; index++)
      {
         if (a[index].compareTo(min) < 0)
         {
            min = a[index];
            indexOfMin = index;
            // Assertion: min is the smallest of a[first] through a[index].
         } // end if
      } // end for
      return indexOfMin;
   } // end getIndexOfSmallest
// -------------------------------------------------------------------------------

  // ALTERNATE VERSION
        public static > 
               void selectionSort2(T[] a, int n)
        {
                selectionSort2(a, 0, n - 1);
        } // end selectionSort2
        
        public static > 
                                 void selectionSort2(T[] a, int first, int last)
        {
                if (first < last)
                { // place the largest value at end of array:
                        swap(a, getIndexOfLargest(a, first, last), last);
                        selectionSort2(a, first, last - 1 );
                } // end if
        } // end selectionSort2

   // Returns the index of the largest value in a portion of an 
        private static > 
                int getIndexOfLargest(T[] a, int first, int last)
        {
                T max = a[first];
                int indexOfMax = first;
                for (int index = first+1; index <= last; index++)
                {
                        if (a[index].compareTo(max) > 0)
                        {
                                max = a[index];
                                indexOfMax = index;
                                // Assertion: max is the largest of a[first] through a[index].
                        } // end if
                } // end for

                return indexOfMax;
        } // end getIndexOfLargest
// -------------------------------------------------------------------------------

// INSERTION SORT
        public static >
           void insertionSort(T[] a, int n)
        {
                insertionSort(a, 0, n - 1);
        } // end insertionSort
        
   public static >
          void insertionSort(T[] a, int first, int last)
   {
      if (first < last)
      {
         // Sort all but the last entry
         insertionSort(a, first, last - 1);

         // Insert the last entry in sorted order
         insertInOrder(a[last], a, first, last - 1); 
      } // end if
   } // end insertionSort
// -------------------------------------------------------------------------------
        
        // ALTERNATE VERSION
        public static > 
               void insertionSort2(T[] a, int n)
        {
                insertionSort2(a, 0, n - 1);
        } // end insertionSort2

        public static >
          void insertionSort2(T[] a, int first, int last)
        {
                if (first < last)
                {
                        insertionSort2(a, first, last - 1);         // Sort all but last item
                        insertInOrder(a[last], a, first, last - 1); // Insert last item in sorted order
                } // end  if
        } // end insertionSort2

        // Inserts element into the sorted array elements a[begin] through a[end]. 
        private static >
           void insertInOrder(T element, T[] a, int begin, int end)
        {       
                if (element.compareTo(a[end]) >= 0)
                        a[end + 1] = element;
                else if (begin < end)
                {
                        a[end + 1] = a[end];
                        insertInOrder(element, a, begin, end - 1);
                } 
                else
                {
                        a[end + 1] = a[end];
                        a[end] = element;
                } // end if
        } // end insertInOrder

// -------------------------------------------------------------------------------

// BUBBLE SORT
        public static >
         void recursiveBubbleSort(T[] a, int n)
        {
                if (n > 1)
                {       
                        for (int index = 0; index < n - 1; index++)
                                order(a, index, index + 1);
                                
                        recursiveBubbleSort(a, n - 1);
                }  // end if
        }  // end recursiveBubbleSort 
// -------------------------------------------------------------------------------

// MERGE SORT
        public static >
               void mergeSort(T[] a, int n)
        {
                mergeSort(a, 0, n - 1);
        } // end mergeSort

   public static >
          void mergeSort(T[] a, int first, int last)
   {
      // The cast is safe because the new array contains null entries
      @SuppressWarnings("unchecked")
      T[] tempArray = (T[])new Comparable[a.length]; // unchecked cast
      mergeSort(a, tempArray, first, last);
   } // end mergeSort
        
        private static >
                void mergeSort(T[] a, T[] tempArray, int first, int last)
        {
           if (first < last)
           {  // sort each half
              int mid = first + (last - first) / 2;  // Index of midpoint
              mergeSort(a, first, mid);              // Sort left half array[first..mid]
              mergeSort(a, mid + 1, last);           // Sort right half array[mid+1..last]

                        if (a[mid].compareTo(a[mid + 1]) > 0)      // Question 2, Chapter 9
                        merge(a, tempArray, first, mid, last);  // merge the two halves
           //   else skip merge step
           }  // end if
        }  // end mergeSort
        
        private static > 
                void merge(T[] a, T[] tempArray, int first, int mid, int last)
        {
                // Two adjacent subarrays are a[beginHalf1..endHalf1] and a[beginHalf2..endHalf2].
                int beginHalf1 = first;
                int endHalf1 = mid;
                int beginHalf2 = mid + 1;
                int endHalf2 = last;

                // While both subarrays are not empty, copy the
           // smaller item into the temporary array
                int index = beginHalf1; // Next available location in tempArray
                for (; (beginHalf1 <= endHalf1) && (beginHalf2 <= endHalf2); index++)
           {  // Invariant: tempArray[beginHalf1..index-1] is in order
           
              if (a[beginHalf1].compareTo(a[beginHalf2]) < 0)
              {  
                tempArray[index] = a[beginHalf1];
                 beginHalf1++;
              }
              else
              {  
                tempArray[index] = a[beginHalf2];
                 beginHalf2++;
              }  // end if
           }  // end for

           // Finish off the nonempty subarray

           // Finish off the first subarray, if necessary
           for (; beginHalf1 <= endHalf1; beginHalf1++, index++)
              // Invariant: tempArray[beginHalf1..index-1] is in order
              tempArray[index] = a[beginHalf1];

           // Finish off the second subarray, if necessary
                for (; beginHalf2 <= endHalf2; beginHalf2++, index++)
              // Invariant: tempa[beginHalf1..index-1] is in order
              tempArray[index] = a[beginHalf2];
                
           // Copy the result back into the original array
           for (index = first; index <= last; index++)
              a[index] = tempArray[index];
        }  // end merge
// -------------------------------------------------------------------------------

// QUICK SORT
   /** Sorts an array into ascending order. Uses quick sort with
       median-of-three pivot selection for arrays of at least
       MIN_SIZE entries, and uses insertion sort for other arrays. */
        public static >
          void quickSort(T[] array, int n)
        {
                quickSort(array, 0, n - 1);
        } // end quickSort

   public static >
          void quickSort(T[] a, int first, int last)
   {
      if (last - first + 1 < MIN_SIZE)
      {
         insertionSort(a, first, last);
      }
      else
      {
         // Create the partition: Smaller | Pivot | Larger
         int pivotIndex = partition(a, first, last);

         // Sort subarrays Smaller and Larger
         quickSort(a, first, pivotIndex - 1);
         quickSort(a, pivotIndex + 1, last);
      } // end if
   } // end quickSort

   //  Partitions an array as part of quick sort into two subarrays
   //  called Smaller and Larger that are separated by a single
   //  entry called the pivot.
   //  Entries in Smaller are <= pivot and appear before the
   //  pivot in the array.
   //  Entries in Larger are >= pivot and appear after the
   //  pivot in the array.
   //  Parameters:
   //     a      An array of Comparable objects.
   //     first  The integer index of the first array entry;
   //            first >= 0 and < a.length.
   //     last   The integer index of the last array entry;
   //            last - first >= 3; last < a.length.
   //   Returns the index of the pivot.
   private static >
           int partition(T[] a, int first, int last)
   {
      int mid = first + (last - first) / 2;
      sortFirstMiddleLast(a, first, mid, last);

      // Assertion: The pivot is a[mid]; a[first] <= pivot and 
      // a[last] >= pivot, so do not compare these two array entries
      // with pivot.

      // Move pivot to next-to-last position in array
      swap(a, mid, last - 1);
      int pivotIndex = last - 1;
      T pivotValue = a[pivotIndex];

      // Determine subarrays Smaller = a[first..endSmaller]
      // and                 Larger  = a[endSmaller+1..last-1]
      // such that entries in Smaller are <= pivotValue and
      // entries in Larger are >= pivotValue; initially, these subarrays are empty

      int indexFromLeft = first + 1; 
      int indexFromRight = last - 2;

      boolean done = false;
      while (!done)
      {
         // Starting at beginning of array, leave entries that are < pivotValue;
         // locate first entry that is >= pivotValue; you will find one,
         // since last entry is >= pivot
         while (a[indexFromLeft].compareTo(pivotValue) < 0)
            indexFromLeft++;

         // Starting at end of array, leave entries that are > pivot;
         // locate first entry that is <= pivot; you will find one, 
         // since first entry is <= pivot

         while (a[indexFromRight].compareTo(pivotValue) > 0)
            indexFromRight--;

         assert a[indexFromLeft].compareTo(pivotValue) >= 0 &&
                a[indexFromRight].compareTo(pivotValue) <= 0;
              
         if (indexFromLeft < indexFromRight)
         {
            swap(a, indexFromLeft, indexFromRight);
            indexFromLeft++;
            indexFromRight--;
         }
         else 
            done = true;
      } // end while

      // Place pivotValue between the subarrays Smaller and Larger
      swap(a, pivotIndex, indexFromLeft);
      pivotIndex = indexFromLeft;

      // Assertion:
      //   Smaller = a[first..pivotIndex-1]
      //   Pivot = a[pivotIndex]
      //   Larger = a[pivotIndex+1..last]

      return pivotIndex; 
   } // end partition

   //  Sorts the first, middle, and last entries of an array into ascending order.
   //  Parameters:
   //     a      An array of Comparable objects.
   //     first  The integer index of the first array entry;
   //            first >= 0 and < a.length.
   //     mid    The integer index of the middle array entry.
   //     last   The integer index of the last array entry;
   //            last - first >= 2, last < a.length.
   private static >
           void sortFirstMiddleLast(T[] a, int first, int mid, int last)
   {
      order(a, first, mid); // Make a[first] <= a[mid]
      order(a, mid, last);  // Make a[mid] <= a[last]
      order(a, first, mid); // Make a[first] <= a[mid]
   } // end sortFirstMiddleLast

   // Orders two given array elements into ascending order
   // so that a[i] <= a[j].
   private static >
           void order(T[] a, int i, int j)
   {
      if (a[i].compareTo(a[j]) > 0)
         swap(a, i, j);
   } // end order

   // Swaps the array entries array[i] and array[j]. 
   private static void swap(Object[] array, int i, int j)
   {
      Object temp = array[i];
      array[i] = array[j];
      array[j] = temp; 
   } // end swap
} // end ArraySorter

Name.java:

/**
   A mutable class that represents a person's name.
   @author Frank M. Carrano
   @author Timothy M. Henry
   @version 4.0
*/
public class Name implements Comparable
{
        private String first; // First name
        private String last;  // Last name

        public Name()
        {
                this("", "");
        } // end default constructor

        public Name(String firstName, String lastName)
        {
                first = firstName;
                last = lastName;
        } // end constructor

        public void setName(String firstName, String lastName)
        {
                setFirst(firstName);
                setLast(lastName);
        } // end setName

        public String getName()
        {
                return toString();
        } // end getName

        public void setFirst(String firstName)
        {
                first = firstName; 
        } // end setFirst

        public String getFirst()
        {
                return first;
        } // end getFirst

        public void setLast(String lastName)
        {
                last = lastName;
        } // end setLast

        public String getLast()
        {
                return last;
        } // end getLast

        public void giveLastNameTo(Name aName)
        {
                aName.setLast(last);
        } // end giveLastNameTo

        public String toString()
        {
                return first + " " + last;
        } // end toString
   
   public int compareTo(Name other)
   {
      int result = last.compareTo(other.last);
      
      // If last names are equal, check first names
      if (result == 0)
         result = first.compareTo(other.first);
         
      return result;
   } // end compareTo
} // end Name

Artist.java:

/**
   A mutable class that represents a person's name.
   @author Frank M. Carrano
   @author Timothy M. Henry
   @version 4.0
*/
public class Artist implements Comparable, java.io.Serializable
{
        private String first; // First name
        private String last;  // Last name

        public Artist()
        {
                this("", "");
        } // end default constructor

        public Artist(String firstName, String lastName)
        {
                first = firstName;
                last = lastName;
        } // end constructor

        public void setName(String firstName, String lastName)
        {
                setFirst(firstName);
                setLast(lastName);
        } // end setName

        public String getName()
        {
                return toString();
        } // end getName

        public void setFirst(String firstName)
        {
                first = firstName;
        } // end setFirst

        public String getFirst()
        {
                return first;
        } // end getFirst

        public void setLast(String lastName)
        {
                last = lastName;
        } // end setLast

        public String getLast()
        {
                return last;
        } // end getLast

        public void giveLastNameTo(Name aName)
        {
                aName.setLast(last);
        } // end giveLastNameTo

        public String toString()
        {
                return first + " " + last;
        } // end toString

   public int compareTo(Artist other)
   {
      int result = last.compareTo(other.last);

      // If last names are equal, check first names
      if (result == 0)
         result = first.compareTo(other.first);

      return result;
   } // end compareTo
} // end Name

Driver.java:

/**
   A driver that demonstrates the class ArraySorter.

   @author Frank M. Carrano
   @author Timothy M. Henry
   @version 4.0
*/
public class Driver
{
   private static final Name[] items =
   {
           new Name("Zeke",  "Clayton"), new Name("Bob",   "Clayton"), new Name("Rob",   "Smith"),
           new Name("Ali",   "Babba"),   new Name("Jamie", "Perfect"), new Name("Jody",  "Perfect"),
           new Name("Jim",   "Smith"),   new Name("John",  "Clayton"), new Name("Bill",  "Smith"),
           new Name("Jamie", "Perfect"), new Name("Zeke",  "Clayton")
   };

        public static void main(String[] args)
        {
                for (int count = 11; count > 0; count = count - 5)
                {
                        System.out.println(count + " items in array.");
/*
                        testSort(1, false, "selection sort", count);
                        testSort(2, false, "selection sort 2", count);
                        testSort(3, false, "insertion sort", count);
                        testSort(4, false, "insertion sort 2", count);
                        testSort(5, false, "bubble sort", count);
                        */
                        testSort(6, true, "merge sort", count);
                        testSort(7, true, "quick sort", count);
                } // end for
        }  // end main

   public static void testSort(int sort, boolean print, String name, int n)
   {
      System.out.println("\nTesting " + name + ":");

      Name[] array = new Name[25];
      copyArray(array, items);
      System.out.println("\nBefore sort:");
      display(array, n);

      if (print)
      {
         System.out.println("\n--------------------");
         display(array, n);
      } // end if

      switch (sort)
      {
         case 1: ArraySorter.selectionSort(array, n); break;
         case 2: ArraySorter.selectionSort2(array, n); break;
         case 3: ArraySorter.insertionSort(array, n); break;
         case 4: ArraySorter.insertionSort2(array, n); break;
         case 5: ArraySorter.recursiveBubbleSort(array, n); break;
         case 6: ArraySorter.mergeSort(array, n); break;
         case 7: ArraySorter.quickSort(array, n); break;
      } // end switch

      if (print)
      {
         System.out.println("After sort:");
         display(array, n);
      } // end if

      check(array, n);
   } // end testSort

        public static void display(Object[] array, int n)
        {
                for (int index = 0; index < n; index++)
                        System.out.println(array[index]);
                System.out.println();
        } // end display

        public static void copyArray(Object[] copy, Object[] array)
        {
                for (int index = 0; index < array.length; index++)
                        copy[index] = array[index];
        } // end copyArray

        public static void check(Name[] array, int n)
        {
                if (isSorted(array, n))
                        System.out.println("Method works.\n");
                else
                        System.out.println("Method DOES NOT work!!!!!!!!!!!!!!!!!!!!!!!!\n");
        } // end check

        public static boolean isSorted(Name[] array, int n)
        {
                boolean sorted = true;
                for (int index = 0; sorted && (index < n - 1); index++)
                {
                        if (array[index].compareTo(array[index + 1]) > 0)
                                sorted = false;
                } // end for

                return sorted;
        } // end isSorted
}  // end Driver

/*
 11 items in array.

 Testing selection sort:

 Before sort:
 Zeke Clayton
 Bob Clayton
 Rob Smith
 Ali Babba
 Jamie Perfect
 Jody Perfect
 Jim Smith
 John Clayton
 Bill Smith
 Jamie Perfect
 Zeke Clayton

 Method works.


 Testing selection sort 2:

 Before sort:
 Zeke Clayton
 Bob Clayton
 Rob Smith
 Ali Babba
 Jamie Perfect
 Jody Perfect
 Jim Smith
 John Clayton
 Bill Smith
 Jamie Perfect
 Zeke Clayton

 Method works.


 Testing insertion sort:

 Before sort:
 Zeke Clayton
 Bob Clayton
 Rob Smith
 Ali Babba
 Jamie Perfect
 Jody Perfect
 Jim Smith
 John Clayton
 Bill Smith
 Jamie Perfect
 Zeke Clayton

 Method works.


 Testing insertion sort 2:

 Before sort:
 Zeke Clayton
 Bob Clayton
 Rob Smith
 Ali Babba
 Jamie Perfect
 Jody Perfect
 Jim Smith
 John Clayton
 Bill Smith
 Jamie Perfect
 Zeke Clayton

 Method works.


 Testing bubble sort:

 Before sort:
 Zeke Clayton
 Bob Clayton
 Rob Smith
 Ali Babba
 Jamie Perfect
 Jody Perfect
 Jim Smith
 John Clayton
 Bill Smith
 Jamie Perfect
 Zeke Clayton

 Method works.


 Testing merge sort:

 Before sort:
 Zeke Clayton
 Bob Clayton
 Rob Smith
 Ali Babba
 Jamie Perfect
 Jody Perfect
 Jim Smith
 John Clayton
 Bill Smith
 Jamie Perfect
 Zeke Clayton

 Method works.


 Testing quick sort:

 Before sort:
 Zeke Clayton
 Bob Clayton
 Rob Smith
 Ali Babba
 Jamie Perfect
 Jody Perfect
 Jim Smith
 John Clayton
 Bill Smith
 Jamie Perfect
 Zeke Clayton

 Method works.

 6 items in array.

 Testing selection sort:

 Before sort:
 Zeke Clayton
 Bob Clayton
 Rob Smith
 Ali Babba
 Jamie Perfect
 Jody Perfect

 Method works.


 Testing selection sort 2:

 Before sort:
 Zeke Clayton
 Bob Clayton
 Rob Smith
 Ali Babba
 Jamie Perfect
 Jody Perfect

 Method works.


 Testing insertion sort:

 Before sort:
 Zeke Clayton
 Bob Clayton
 Rob Smith
 Ali Babba
 Jamie Perfect
 Jody Perfect

 Method works.


 Testing insertion sort 2:

 Before sort:
 Zeke Clayton
 Bob Clayton
 Rob Smith
 Ali Babba
 Jamie Perfect
 Jody Perfect

 Method works.


 Testing bubble sort:

 Before sort:
 Zeke Clayton
 Bob Clayton
 Rob Smith
 Ali Babba
 Jamie Perfect
 Jody Perfect

 Method works.


 Testing merge sort:

 Before sort:
 Zeke Clayton
 Bob Clayton
 Rob Smith
 Ali Babba
 Jamie Perfect
 Jody Perfect

 Method works.


 Testing quick sort:

 Before sort:
 Zeke Clayton
 Bob Clayton
 Rob Smith
 Ali Babba
 Jamie Perfect
 Jody Perfect

 Method works.

 1 items in array.

 Testing selection sort:

 Before sort:
 Zeke Clayton

 Method works.


 Testing selection sort 2:

 Before sort:
 Zeke Clayton

 Method works.


 Testing insertion sort:

 Before sort:
 Zeke Clayton

 Method works.


 Testing insertion sort 2:

 Before sort:
 Zeke Clayton

 Method works.


 Testing bubble sort:

 Before sort:
 Zeke Clayton

 Method works.


 Testing merge sort:

 Before sort:
 Zeke Clayton

 Method works.


 Testing quick sort:

 Before sort:
 Zeke Clayton

 Method works.


*/

Answer 1

"Public class my merge sort { Private int[] arrat: Private int [] tem merge Arr: Private int length: Public static void main (String args[]) { int[] input Arr = {45, 23, 11, 89, 77, 98, 4, 28,65 Mymergesort mms = new mymergesort (): mms.sort (input Arr): \r\n for (int i: input Arr) { system.out.print (i): system.out.print ("" ""): } } Public void solt (int input Arr[]) { this. array = input Arr: this. length = input Arr.length: this. tempmergeArr = new [length]: do merge Solt (0, length - 1): } Private void do merge solt(int lower index, int higher Index) { if (lower Index < higher Index) { int middle = lower Index + (higher Index - lower Index) 2 do merge solt (lower Index, middle): do merge solt (middle + 1, higher Index): Merg Palts (lower Index, middle, higher Index): } } Private void merge palts (int lower"