CMPSC-132: Programming and Computation II
Fall 2018
Lab #13
Due Date: 11/18/2018, 11:59PM
Instructions:
– The work in this lab must be completed alone and must be your own. Do not copy code
from online sources. That is considered plagiarism.
– Use the starter code provided on this CANVAS assignment. Do not change the function
names or given started code on your script
– The file name must be LAB13.py (incorrect name files will get a -1 point deduction)
– A doctest is provided as an example of code functionality. Getting the same result as
the doctest does not guarantee full credit. You are responsible for testing your code
with enough data as possible.
– Each function must return the output (Do not use print in your final submission otherwise,
you will get a -1 pt deduction)
– Do not include test code outside any function in the upload. Remove all your testing code
before uploading your file. Do not include the input() function in your submission.
Goal
[10 pts]. As discussed in class, merge sort is a sorting algorithm that continually splits a list in half
following the divide and conquer strategy. Once two halves are sorted, the fundamental operation
“merge” is performed. Write the functions merge(list1, list2) and mergeSort(numList) to correctly
sort a list of numbers. mergeSort is a recursive function that calls merge to return the final sorted
list.
You are not allowed to use the sorted() method or the sort operator. Your code will not get
credit if you use them
mergeSort must be a recursive function, otherwise, your code will not get credit
Remember:
– If the list is empty or has one item, it is sorted by definition
– Merging is the process of taking two smaller sorted lists and combining them together into
a single, sorted, new list
EXAMPLES:
>>> mergeSort([12,35,87,26,9,28,7])
[7, 9, 12, 26, 28, 35, 87]
>>> merge([12,26,35,87],[7,9,28])
[7, 9, 12, 26, 28, 35, 87]
>>> merge([12,35],[26,87])
[12, 26, 35, 87]
Deliverables:
Submit your code in a file name LAB13.py to the Lab13 CANVAS assignment before the
due date