Lab 18.2 Recursive MergeSort

Assignment

1. Using your code template from Lesson 17 as a starting point, write a recursive mergeSort method as described in the student lesson. Pseudocode for the recursive mergeSort method is given below.

   // Recursively divides a list in half, over and over. When the
   // sublist has one or two values, stop subdividing.
   void mergeSort(ArrayList <Comparable> a, int first, int last) {
        if (sublist has only one value) {
                   // do nothing
        } else if (sublist has two values) {
                   // sort it if necessary
        } else { // recursion, divide list into two halves
                   // Find midpoint of current sublist
                   // Call mergeSort and process left sublist
                   // Call mergeSort and process right sublist
                   // merge left and right sublists
        }
   }
   

   Note that you will have to rewrite a new merge to fit the necessary calls of the new mergeSort method.

2. For both mergeSort() and merge() you must work with the single ArrayList parameter that is passed in. (i.e. You may not modify the merge() method to accept more ArrayLists.) However, you are free to create a temporary list within the merge method.

3. If you want an extra challenge, try writing the merge() method without using a temporary list. This is possible with ArrayLists.

Instructions

1. Complete the merge and mergeSort methods within your code template from Lesson 17.

2. Add the necessary code to count steps. Note that since mergeSort calls merge, you will need to include step counting there as well.

3. Repeat steps 5 to 7 from Lab 17.4, including mergeSort in your graphs.

   	100 integers	200 integers	400 integers	800 integers
   BubbleSort	___	___	___	___
   SelectionSort	___	___	___	___
   InsertionSort	___	___	___	___
   MergeSort	___	___	___	___

Submission

• Upload your updated PX_LastName_FirstName_Sorts.java code below that includes recursive mergeSort and merge.
• Turn in your updated data table and graph in person or via the Schoology assignment page

You must Sign In to submit to this assignment