Skip to main content
ICT
Lesson A18 - Merge and MergeSort
 
Main   Previous
 

LAB ASSIGNMENT A18.2 page 9 of 9

Recursive MergeSort

Assignment:

  1. Using the merge program in Lab Assignment A18.1, Merge 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 las)
    {
       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
       }
    }

  2. You will have to modify the merge method to fit the necessary calls of the mergeSort method.

Instructions:

  1. After confirming that your mergesort works, paste the necessary routines into your sorting template program (MergeTemplate.java) and count the number of steps for a recursive mergesort. Record the number of steps on the worksheet from Lab Assignment A17.1, QuadSort.

  2. Turn in your source code and a printed run output of 100 numbers, sized from 1-200. If possible, print only merge and mergeSort methods.

 

Main   Previous
Contact
 © ICT 2006, All Rights Reserved.