The Problem Its the first day of class and you are barely awake. You are hoping to snooze through a typical syllabus day when your new teacher commands you to get up and find the person in the room with the closest birthday to yours. Luckily, youve learned some sorting algorithms already and realize that the key to solving the problem is to sort EVERYONE by their birthday, and then simply look directly to the left and right of you (the birthday that occurs immediately before and after yours) and see which of the two is closer. If you on the end of the list, you have to check with the person at the beginning and vice versa.

In order to solve this problem, youll get several different classes from an input file. Each class will have several queries. You are required to implement either MergeSort or Selection/InsertionSort in the solution of your assignment.

Input File Specification (birthday.txt) The input file has a single positive integer, n, on its first line, specifying the number of classes in the input file.

The first line of each input file will have a single positive integer k (1 < k < 1001), representing the number of students in the class. The next k lines will have information about each student. Each line will have the following information separated by spaces: first name, last name, month, day and year of birth. All names will only contain uppercase alphabetic characters and be no longer than 29 characters long. The month will be represented in its full spelling, in uppercase letters. The day and year will be the appropriate integers. You are guaranteed that all of this information is valid. (Thus, no April 31 st will appear, etc.) It is also guaranteed that each full name will be unique. (Namely, no two people in a class will have the exact same first AND last name.)

Following those k lines will be a line containing a single positive integer m (m < k), representing the number of queries for that class. The following m lines will contain the first and last name (separated by a space) of the student in question. (Your goal will be to find the name of the student with the closest birthday to the queried student.)

Output Specification For each input class, print out a header with the following format:

Class #c:

where c represents the day of the simulation (1 c n).

Follow this with a blank line.

The following k lines will answer the queries for that class in the order they were given. For each of these queries, output a single line with the following format:

FIRST2 LAST2 has the closest birthday to FIRST LAST.

where FIRST LAST is the name of the queried student and FIRST2 LAST2 is the name of the student with the closest birthday to FIRST LAST.

To avoid ambiguity, sort the students in the following manner:

1) By birthdate, ignoring the year.

2) To break ties between students with the same exact birthdate, use last name as compareTo function.

3) To break ties where both #1 and #2 are the same, use the first name, which in these cases, is guaranteed to be different.

To further avoid ambiguity, if both the person who appears right before and right after the queried person are the same number of days away (in birthday) as the queried person, always choose the person who comes AFTER the queried person in the array. If the queried person is the LAST person in the array, then the person in index 0 will be considered as the person who comes AFTER them. Note: for these purposes, February 29 th wont count as an actual day, unless someone in the class has that birthday. For example, if the queried persons birthday is March 1 st , the person right before her has a February 28 th birthday and the person right after her as a March 3 rd birthday, then the person with the February 28 th birthday is considered the closest (1 day way) as compared to the March 3 rd birthday (2 days away). BUT, if there IS a February 29 th birthday in the class, then that does count as a day.

Put a blank line between the output for each case.

Implementation Restrictions

You must store all the relevant information about a student in an appropriate data structure. You must implement either MergeSort or Selection/InsertionSort. You must follow all the tie- breaking procedures described above.

Sample Input File

2

3

ROSIE JUAREZ MAY 3 1961

SEEMA PATEL AUGUST 16 1970

ARASH BENCHKROUN DECEMBER 12 1955

2

ROSIE JUAREZ

ARASH BENCHKROUN

4

BORIS GAVIRIA SEPTEMBER 15 1961

ARISA POULSON JUNE 28 1960

JOSUE NGUYEN JUNE 11 1956

DAN IRWIN JUNE 10 1951

1

JOSUE NGUYEN

Sample Output

Class #1:

SEEMA PATEL has the closest birthday to ROSIE JUAREZ.

SEEMA PATEL has the closest birthday to ARASH BENCHKROUN.

Class #2:

DAN IRWIN has the closest birthday to JOSUE NGUYEN.

The program used is Java. Here is what I have so far

https://pastebin.com/mrC47DNE https://pastebin.com/Tx2xVTrX

textfile https://pastebin.com/Grkk8vLR

I need to know how to implement a Merge Sort for the problem and create an OutputFile for the birthdays being compared. Futhermore, I need to create a text file with the strings of birthdays being compared printed out just like the Output sample.

I tried to make it by putting it in the Birthday class in the main method before the collectInfo() method was called in the main like so.

File file = new File("birthdayOutput.txt");

FileOutputStream fOS = new FileOutputStream(file);

PrintStream ps = new PrintStream(fOS);

System.setOut(ps);

but as I compiled it, I got blank as an output after compiling. I should not get that. I need the answer to come out as both console and as text file.