Last time we learned about how to use/implement the merge sort, and we also talked about how Java uses the merge sort by default.

In this assignment, you are going to be given a file that reads a data file for a number of values, and then sorts them by name. This has been done for you and uses the default Collections.sort. However we also want to be able to sort the users by the ID number.

Your assignment is to implement the merge sort on the array of people, but you will need to use the ID as the key to determine what order they go in. You will not be able to use the default sort since it uses the compareTo method, but you need to compare based on something else.

Download the main program, the two data files, and then find the method that you need to implement and implement it. You may also need to implement additional methods to make it work.

The program does time your algorithm, so I would encourage you to try to make it as fast as you can, and you can compare your version to the default sort to see how you are doing.

The Files:

MergeSortTesting.java

public class MergeSortTesting { private List myList= new ArrayList(); public static void main(String[] args) { MergeSortTesting obj = new MergeSortTesting(); obj.run(); } public void run() { //MAKE SURE TO UNCOMMENT ONE OF THE LINES BELOW File f = new File("DataFileInClass5.txt"); //File f = new File("DataFileInClass5ver2.txt"); Scanner scan = null; try { scan = new Scanner(f); } catch (FileNotFoundException e) { System.out.println("File Not found"); System.exit(0); } while(scan.hasNext()) { int i = scan.nextInt(); String a = scan.next(); String b = scan.next(); Person temp = new Person(i,a,b); myList.add(temp); // System.out.println(temp); } //System.out.println(myList); long startTime = System.currentTimeMillis(); Collections.sort(myList); long endTime = System.currentTimeMillis(); sortListByID(myList); long endTime2 = System.currentTimeMillis(); System.out.println("Checking the order"); for (int i=0;i { private String fName; private String lName; private int ID; public int getID() {return ID;} public String getName() {return fName + " " + lName;} Person(int a, String b, String c) { fName = b; lName = c; ID = a; } public String toString() {return "["+lName +", " + fName + " #" + ID+"]";} public int compareTo(Person o) { if (lName.compareTo(o.lName)==0) return fName.compareTo(o.fName); else return lName.compareTo(o.lName); } } private static void sortListByID (List theList) { //TODO // WRITE YOUR MERGE SORT HERE // MAKE SURE TO SORT BY ID // } }

DataFileInClass5.txt

91058312 Malika Schulman 69807422 Krysta Lorraine 8927564 Suk Cesar 196816038 Magda Kastner 194671164 Antone Brunell 105752387 Jeannette Luse 87833366 Dorotha Costigan 178889081 Elina Crandall 185162708 Jerrold Schrimsher 33395580 Magan Frier

Helpful Notes:

To make a copy of a part of a list, use the following approach

List> smallerVersion = new ArrayList>()

smallerVersion.addAll( originalList.subList(startPoint,endPoint) )

Take a look at the Person class, to see what you have access to.

Don't be afraid to look at the prior notes for help with the merge sort.