In this tick you will implement a memory-efficient version of mergesort, mentioned at the end of section 2.9 in lecture notes.
This mergesort is bottom-up, as opposed to the standard top-down (recursive) version. In the first pass, it groups elements into pairs and sorts each pair by merging two chunks of size 1. In the second pass, it groups elements into quadruples and sorts each quadruple by merging two chunks of size 2. In the next pass, it merges these quadruples into sorted octuples. And so on, until the entire array is sorted. Note that most chunk sizes are a power of two, but the final chunk in each pass may be smaller. Here is the sequence of merges involved in sorting an array of length 7:
To merge two chunks, the strategy is to copy the right-hand chunk into scratch space, then merge the two chunks back into the original array. The merge should be performed right-to-left in order to avoid overwriting values from the left-hand chunk. You are given a scratch space of size floor(n/2). (It’s this tight limit on scratch space that forces us to merge in this way. In the example above with \(n=7\), the final step merges a chunk of size 4 and a chunk of size 3, and the scratch space is too small to fit the size-4 chunk.)
Prof Stajano has made a video explaining bottom-up mergesort, which you may find helpful.
I asked ChatGPT for code, and its two attempts are both incorrect. Nonetheless, it has the general idea right.
Task 1. Demonstrate that ChatGPT’s code doesn’t work. You should find an array which causes ChatGPT’s mergesort1 to fail with an exception, and another array for which mergesort2 doesn’t trigger an exception but does result in an incorrect answer. Both arrays should have size > 4.
Task 2. Implement the mergesort algorithm described above. For the tester to verify that your code is indeed working on chunks bottom-up, your mergesort function should accept an extra argument is_sorted, and you should call is_sorted(i,j) just after you have merged the two chunks that that make up the range x[i:j]. The tester will verify that x[i:j] is indeed in order. Your final call should be is_sorted(0,n) where \(n\) is the length of the array.
In your code, you must use only the arrays provided by the tester—the array to be sorted, and the scratch space. The idea is to make you painfully conscious of how memory is being used in your code!
- Don’t create extra Python lists yourself.
- Don’t use slice notation (e.g.
scratch[:a] = x[i:i+a]), instead copy items yourself one by one.- Don’t copy values out of the array and then back in, for example
v=x[0]; x[0]=x[1]; x[1]=v. If you do then the operation will fail with a CopyError. Instead, use the scratch array.
Submission filename: mergesort.py. Please submit on moodle a source file that implements these three functions:
# Produce examples that demonstrate problems with ChatGPT's code
# Each function should simply return a list of length >= 4.
# (Your functions should NOT call mergesort1 or mergesort2, they should
# simply return your examples. The tester will then call mergesort1/2.)
counterexample1()
counterexample2()
# Sort an array using the provided scratch space,
# which has size floor(len(x)/2).
# The function has no return value, but the array x should end up sorted.
mergesort(x, scratch, is_sorted)If you want to see what input array is being fed into your code, just stick in print(x) and you’ll see it in the output log on Moodle when your code is evaluated.