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(" Testing " + name + ":"); Name[] array = new Name[25]; copyArray(array, items); System.out.println(" Before sort:"); display(array, n); if (print) { System.out.println(" --------------------"); 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. "); else System.out.println("Method DOES NOT work!!!!!!!!!!!!!!!!!!!!!!!! "); } // 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. */