Using Merge Sort:

In this project, we combine the concepts of Recursion and Sorting. Since the Java Collection API provides various built-in sorting capabilities, so we will focus on Merge Sort and have it applied to a file.

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 "p6sortedArts.txt" which is sorted ascendingly on artistID and then artID both.

Example follows:

(sample output just for artistID) (have to sort both, ArtistID and then ArtID):

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

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.

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:

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 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. */