The template includes a Email class, which consists of two instance variables: sender, which is a string representing the name of the person or entity who sent the email, and subject, which is a string representing the subject line of the email. The file also includes some test cases representing sample inboxes for Holistic Synergies, Ltd. employees. Youll need to implement Merge Sort and Quicksort algorithms which operate on a list of Email objects, and sort them in non-increasing order by the length of the sender string (that is, longest sender name to shortest).

Requirements: You must download the template file PA3.py and edit the merge, merge_sort, partition, and quick_sort functions. Do not edit any other part of the file. Your program must run without errors on the version of Python installed on the CSELabs machines, Python 3.5.2. (if youre testing this on CSELabs, you need to type python3 or idle3 instead of python or idle to start the correct version from the terminal) You are not permitted to use any built-in Python sorting routines like the sorted() function or the .sort() list method. You are also not allowed to use any Python function that asks for user input, such as input(), as this will break the grading script. You may not import any modules other than traceback, which is already imported by the template. You must implement the Quicksort and Merge Sort algorithms as described in the textbook. Any other sorting algorithms will receive very little credit, even if you pass every test case. However, note that while the textbook algorithms describe how to sort a list of numbers in non-decreasing order, this problem requires you to sort a list of Email objects in non-increasing order by length of sender name, so you will need to adjust the algorithm slightly. The textbook version of Merge Sort is a stable algorithm; your Merge Sort must also be stable; the final Merge Sort test case checks this. Quicksort is not stable, so yours does not have to be. You will need to use something in place of the sentinel values used in the textbooks Merge function, since putting into a list of Email objects to be sorted by sender name length doesnt make sense. There is an Email object that you could construct that would work as a sentinel, but if you cant figure that out, feel free to adjust your Merge algorithm to operate without sentinels.

#Takes in list of Emails A, and indices p, q, and r

#Assuming that the sublists A[p...q] and A[q+1...r] are sorted by

#the length of the Email's sender, from longest to shortest,

#merges the two lists together and puts them back into the list

#Returns nothing

def merge(A,p,q,r):

pass

#Takes in list of Emails A, and indices p and r

#Sorts the sublist A[p...r], in order of the length of each Email's

#sender, from longest name to shortest, using Merge Sort

#Returns nothing

def merge_sort(A,p,r):

pass

#Takes in list of Emails A, and indices p and r

#Chooses A[r] as a pivot Email and re-orders the list so that

#all Emails with a longer sender name than the pivot come

#before the pivot in the list, and all Emails with a shorter

#sender name come after.

#Returns the index where the pivot is located

def partition(A,p,r):

pass

#Takes in list of Emails A, and indices p and r

#Sorts the sublist A[p...r], in order of the length of each Email's

#sender, from longest name to shortest, using Quicksort

#Returns nothing

def quicksort(A,p,r):

pass