Question: import traceback def merge_sort(A): print(TODO: Implement this function) #Email class #Each email has two instance variables: # self.sender is a string representing the name of
You are placed in charge of the email servers as part of your unpaid internship at Holistic Synergies, Ltd. Your supervisor, Dr. Boss Manager III, has compromised company security by leaking data to hackers over email on multiple occasions. However, he has a solution. After watching a certain sci-fi movie series, Dr. Manager has come to the conclusion that hackers always use short, trendy names like "Neo" or "Cypher". Therefore, rather than displaying emails in order from newest to oldest, he orders you to reprogram the server to display emails from longest sender name to shortest, so that all of the emails from people with short hacker names are pushed to the bottom. Speed is of the utmost importance to Holistic Synergies, Ltd., so you will be implementing this email sorting routine in Merge Sort to guarantee a (nlgn) algorithm. In particular, your boss has heard that recursion tends to be slow in Python, so you need to implement Merge Sort iteratively (no recursive calls). You will likely need at least three nested loops to accomplish this: - One to keep track of how large the sublists you're currently merging are (start at 2, then 4 , then 8 , and so on) - One to cycle through all of the sublists of that size (for example, if you're currently looking at all sublists of size 4 in list A, then you need to look at A[0:4],A[4:8],A[8:12], and so on). - One (or possibly more, depending on how you implement it) to actually do the merge process for the left and right halves of that sublist. Instructions: Download the template pa03.py from the class website. 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. You'll need to implement the Merge Sort algorithm which operates 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). This algorithm should alter the list passed in, rather than return a new list. Remember, Merge Sort should be a stable sorting algorithm - that means that if Email A and Email B have the same sender length and Email A appears before Email B in the input list, Email A should appear before Email B in the output list. You might want to consider adding methods that overwrite one or more of the comparison operators for the Email class - this would allow you to use operators such as : def _gt__(self, other) = : def __ge_(self, other) ==: def ____(self, other) 1=: def _____(self, other) While you're not allowed to use recursion, you are permitted to write helper functions - this may be useful in breaking up and testing different parts of the algorithm. I would recommend implementing the recursive version of merge sort, based on the textbook pseudocode, as a starting point. Then figure out how to write loops to replace the recursion
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help