Parts (c) and (d) are based on the following:

BACKGROUND INFO: This year, thousands of students took the SAT (Scholastic Aptitude Test) in New Jersey in preparation to enter college. The total score on the SAT is out of 2400scores are in multiples of 10. You are asked by the SAT office to write a program that will sort the students in descending values of their scores. If two students have the same score, it does not matter in which order they appear in the sorted result. Assume that the computer on which you will run your program has enough memory to store the names and scores of all the students, either in an array or in a linked list. Also, for this question, you can assume the number of students who took the SAT this year is exactly 65,536, which is 2

c) Assuming you were to use mergesort with linked lists, and counting only each score-to-score comparison as a unit time operation, how many such unit time operatons (not big O) would it take in the worst case to do the sort? Your answer must be simplified to the least possible number of terms.

NOTE FOR PART C: DO NOT WRITE ANY CODE: ONLY COMPUTE UNIT TIME COMPARISONS SHOWING WORK AND LOGIC

d) Come up with an algorithm that is better than mergesort above, i.e. it makes fewer unit time operations in the worst case. State what data structure(s) you will use, and clearly describe your algorithm. Then specify what unit time operations you are counting, and determine the total number of such units. You will NOT get any credit if your algorithm is not better than mergesort for this application, even if it works, and you have analyzed it correctly.

NOTE FOR PART D: DO NOT WRITE ANY CODE: ONLY WRITE AN ALGORITHM TO REDUCE UNIT TIME IN PART C. COMPUTE UNIT TIME FOR NEW ALGORITHM AND SHOW WORK (WHERE UNITS ARE COMING FROM)