Homework 5

due: Thursday March 27 at 11:59pm (submit on Gradescope here).

Goals:

• Implement a variant of MergeSort called TriMergeSort

In this homework, you will implement a variant of the MergeSort algorithm in which arrays are divided into three subarrays (instead of two) during each recursive call to the sorting method. The approach (and resulting code) will be very similar to what we did in class, so please review the implementation of MergeSort we had on slides 8 and 10 of the notes.

Overview of TriMergeSort

Everything will be implemented in the TriMergeSort.java file, which can be downloaded here. Similar to regular MergeSort, the idea of TriMergeSort is to divide the current input array into subarrays, sort the subarrays recursively, and then merge them. This time, however, we will divide the input array into three subarrays instead of two.

Similar to what we did in class, we won't explicitly create these three subarrays - we'll just use indices to represent where the subarrays start and end. The leftmost item of the input array is at items[left] and the rightmost item of the input array is at items[right - 1]. Since we are dividing the interval between left and right into thirds, we need two middle indices (mid1 and mid2), which are already computed for you in the triMergeSortHelper method. The three subarrays are defined as follows:

• The 1st subarray starts at items[left] and ends at (including) items[mid1 - 1].
• The 2nd subarray starts at items[mid1] and ends at (including) items[mid2 - 1].
• The 3rd subarray starts at items[mid2] and ends at (including) items[right - 1].

Part 1: complete the compare method [2 points].

As in regular MergeSort, we need to compare the leading items that remain from the merged subarrays in order to determine which item should be placed back into the merged array. With regular MergeSort we just needed to compare two values, but now we need to compare three values (the remaining minimum from each of the three subarrays). Please complete the compare method to determine the minimum of three items. We don't want to actually return the minimum value, but we'll return a code to inform the merge method which subarray the item is from:

• A return code of -1 indicates the minimum item is the first item (from the first subarray), i.e. items[i].
• A return code of 0 indicates the minimum item is the second item (from the second subarray), i.e. items[j].
• A return code of +1 indicates the minimum item is the third item (from the third subarray), i.e. items[k].

Look at how the compare method is called within the merge method to see how it's used. Note that the inputs (i, j, k) of the compare method represent the indices of the items we want to compare, meaning we want to determine the minimum of items[i], items[j] and items[k].

Part 2: complete the merge method [5 points].

The merge method is partially complete: it retrieves the minimum leading value of the three subarrays until one of the subarrays is empty. Complete this method (see the TODO comments) to continue retrieving the minimum value from the two remaining subarrays. Then proceed to retrieve the minimum value from the last remaining subarray. The code for this part will be very similar to what was done in the in-class exercise, so please review slide 10 of the notes.

Note that by "empty", we mean that the index pointing to the leading element reaches the maximum index of the subarray as in class (nothing is actually "emptied"). The picture below might help visualize the variables in the merge method:

Note that in the example above, the three subarrays (starting at i1, i2 and i3 respectively) are already sorted, as they should be at the beginning of the merge method.

We strongly recommend testing the call to merge within a PSVM before proceeding. You can use the array in the picture above as an example, but might want to come up with other examples to test different scenarios in which different subarrays are emptied first.

Part 3: complete the triMergeSortHelper method [3 points].

Finally, complete the triMergeSortHelper method to complete the TriMergeSort algorithm. This will look very similar to the mergesortHelper from the in-class exercise, except that this time we need to recursively sort three subarrays and then merge them. Note that the mid1 and mid2 indices, which mark the indices at which the second and third subarrays begin are already calculated.

If this part doesn't work, the mostly likely reason is because of a bug in the merge method of Part 2, so we suggest testing that method further to find the source of the bug.

Submission

Upload TriMergeSorter.java to Gradescope. Remember to check the style of your code and add your name to a comment at the top of your file!