TL;DR
Implement a non-recursive and bottom-up mergesort in Python 3, complying with all of the following constraints. Observe that this is not the same as the regular recursive top-down mergesort described in the lecture notes but rather the variant hinted at on page 40 at the end of section 2.9, except with a further refinement to use even less scratch space. The following video might help you understand bottom-up (as opposed to top-down) mergesort: https://youtu.be/cUxOG9O7xNU.
Constraints
You are given a data array of size n and a scratch space array of size n/2 (rounded down if n is odd). You may not allocate any additional memory yourself (creating new lists or arrays, appending items to existing lists etc). Observe that this limitation on the size of the available scratch space means that certain naïve strategies won’t work. For example, when sorting a 17-item array, you won’t be able to park a 16-item chunk into scratch space.
You may not use any Python language or library features (such as the sort() method) to do the sorting.
To support automated testing, the arrays passed to the routine are not native Python lists but rather custom-made Fixed String Arrays from the supplied fsa.py module. You are not allowed to change the fsa.py module nor to create derived classes from nsa.FixedSizeArray. The API of fsa.py is very simple. You create an array of size n with a = fsa.FixedSizeArray(n). You read the value at position i (zero-based) with the expression a[i]. You write to that position by assigning into it, as in a[i] = 345. There are no constraints on the types of the values in the cells, but you may not read from, nor write to, cells outside the range 0 to n-1.
You must copy the supplied bums_template.py to bums.py (standing for Bottom Up Merge Sort) and edit the latter to provide implementations of the following methods: passes(), chunkSizeInPass(), lddr(), mergeRL(), sort(), with the APIs defined in the corresponding docstrings. Some other helper methods are already defined for you and should not be changed. Your sort() method should make good use of the other methods that you were required to implement. (Hint: it is probably a good idea to plan the structure of your code on paper before starting to type away in the editor.)
In your final submission to Moodle, you may not import any other Python modules than the ones already imported by the supplied bums_template.py.
Code that violates any of the above constraints may not earn a tick, even if it passes the autotester. Failing the autotester may help you discover some bugs in your code but passing the autotester is not a guarantee that your code complies with the above constraints nor that it is correct.
Do not cheat. Do not collaborate with others on the tick. Do not copy other people’s code. Do not share your code with others. Any of these actions is liable to attract a severe penalty.
What to do
Download fsa.py and bums_template.py.
Rename bums_template.py to bums.py and edit bums.py, completing missing parts.
Do not change fsa.py.
Debug bums.py until correct, ideally writing your own unit tests.
Optional: ensure your code passes pycodestyle.
Upload your bums.py (but not any other files) to Moodle.
If your code fails the autotester, debug and reupload until it passes.
Hints
Before starting to code, work out all the steps for a test case, for example with n=9. Figure out the correct behaviour of the various methods on that test case before you implement them. You should have 4 passes, with chunk sizes of 1, 2, 4 and 8 respectively; and the last pass should merge a chunk of size 8 and a chunk of size 1 using no more than floor(n/2) = floor(4.5) = 4 cells of scratch space.
Ensuring the validity of a precondition is the job of the caller, not of the callee, so the callee is not responsible for checking that a precondition is met on entry. However, during development, adding such a check may help you debug your implementation by pointing out what the caller did incorrectly, rather than just leaving you to figure out why the callee crashed.