Homework 5
Homework Reflection SurveyGradescopeStarter CodeDue: Thursday October 23, 2025 5:00PM
Goals:- Implement a variant of
MergeSort called TriMergeSort
Submit these files:TriMergeSort.javaIn 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 in class.
Overview of TriMergeSort
Everything will be implemented in the TriMergeSort.java file. 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.
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.
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 the slides.
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.
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.
Test Case Requirements
We’re keeping it simple for test case requirements this week. The only requirement is that you test TriMergeSorter.sort on at least two different arrays!
Documentation, Style, and Design
Documentation and Style
Checkstyle will run automatically when you submit to gradescope; up to 10% will be deducted by the autograder from the programming portion of your grade if you have > 2 types of checkstyle problems. Remember you can see more details on checkstyle on this page, including how to run it in vscode.
Design
I will do a manual review for design. Up to 5% may be deducted from your final score due to design problems. This will also include checking the quality (rather than just the form) of your javadoc comments!