Description
Mergesort [100%]
I am assuming you have seen mergesort in your other courses. Otherwise, do some
independent research on what mergesort is. Understanding how it works is relatively straight
forward.
2
Bottom-up [60%]
Everyone that learns mergesort has seen an image similar to the one below.
Figure 1: Classic top-down mergesort illustration.
Mergesort seems to embody the divide-and-conquer approach. But do we really need to divide?
How about just conquering? What I mean by that is, instead of recursively splitting the list into
smaller parts (from the top down), and then rebuild it. Why not instead start off by viewing
the array/list as already divided, and simply complete the rebuild/merge portion. This is the
essence of the bottom-up implementation. The idea is you iteratively pass through the list and
merge portions of the list based off some window size (see the figure below). The size of the
window increases after each iteration of the loop.
The bottom-up implementation does not make any recursive calls. It is done entirely with
loops. Implement merge sort via a bottom-up approach. Meet the following criteria to achieve
full grades:
• Implement a function mergesort_bottom(L) which takes a single list as input and sorts
that list L.
3
Figure 2: A bottom-up illustration of merge sort. Note the elements being sorted/merged in
the window.
• Implement a helper function merge_bottom(L, start, mid, end). This should merge
the interval [start:end] assuming [start:mid] and [mid:end] are sorted. The exact inclusive/exclusive decisions for the intervals are left up to you. As long as your
mergesort_bottom(L) works.
• Your functions should not be recursive in anyway. Loops only.
• Note, in Figure 2 the length of the list is conveniently a power of 2, this may not be the
case. You will have to resolve this in some way.
Compare this bottom-up implementation to the one I gave you in lab4.py
Three-Way Mergesort [20%]
Traditionally, mergesort divides the list recursively in 2, but why not 3? Do you think this
would be better or worse than a 2 way mergesort? Implement a three-way mergesort via
mergesort_three and merge_three function in your sorts.py file. These functions should
4
be written in the same fashion as mergesort and merge. Compare the performance of the
three-way mergesort vs the traditional two-way.
Worst Case [20%]
Last lab we saw that quicksort has a terrible worst case runtime when the list is sorted or
near sorted. Is the same true for mergesort? Take your best mergesort implementation. Using
the create_near_sorted_list function graph the runtime of mergesort vs factor, for factor
between 0 and 0.5. Keep the length of the list constant throughout your experiments. What
do you observe?
