10 Teach : Team Activity - Merge Sort
Overview
Practice a non-trivial recursive algorithm: Merge Sort
Instructions
Implement the merge sort algorithm.
Begin with the starting template: ta10-template.py. Implement the merge_sort function.
Core Requirements
Correctly split the list into two halves.
Correctly handle the base case, and the recursive calls to merge_sort each half.
Correctly merge the two sorted halves back together. (This is the meat of the assignment...)
Stretch Challenges
After completing the above steps. Make sure that everyone on the entire team is to this point and understands the material. Then, if you have time, move on to the following stretch challenges.
The stretch challenge is to implement quicksort.
Have any necessary methods and a base case in place.
Choose a partition item and put it in its proper place with everything less than it on the left, and everything greater on the right.
Complete the recursive calls to finish the algorithm.
Instructor's Solution
As a part of this team activity, you are expected to look over a solution from the instructor, to compare your approach to that one. One of the questions on the I-Learn submission will ask you to provide insights from this comparison.
Please DO NOT open the solution until you have worked through this activity as a team for the one hour period. At the end of the hour, if you are still struggling with some of the core requirements, you are welcome to view the instructor's solution and use it to help you complete your own code. Even if you use the instructor's code to help you, you are welcome to report that you finished the core requirements, if you code them up yourself.
After working with your team for the one hour activity, click here for the instructor's solution.
Submission
You do not need to submit your program (just make sure that everyone has a copy of it for their reference). Instead, answer the accompanying questions in the I-Learn quiz.