CS 151 -- Lab 8, Nov 10

Merge sort is used by Java to sort objects. It is fast and stable. But it does require some extra memory. In this lab you will implement the merge part of merge sort. You must use the algorithm given below.

When you are done writing your merge implementation, write a method to fill a an ArrayList with N integers, sorted but with random separations; again the algorithm is given below.

Finally, put these two together. In a main, create 2 ArrayLists of 20 and 50 integers respectively integers using the creation function you wrote. Pass these two ArrayLists to your merge function. See that this works.

Merge

Write a merge method according to the following textual description.

    method merge: takes two parameters as given below.
                  returns an arraylist of N+M items in sorted order
    PARAM: list1: a list of N sorted integers
           list2: a list of M sorted integers

    Let: result = an empty list ArrayList of integers
         p1 = 0 // a location in list1
         p2 = 0 // a location in list2
    While p1<N or p2 < M 
        if p1>N 
           add p2th element of list2 to result
           increment p2
        else if p2>M 
            add p1th element of list1 to result
            increment p1
        else
            if p2th element of list2 < p1th element of list1
               add p2th element of list2 to result
               increment p2
            else
               add p1th element of list1 to result
               increment p1
    return result

Build a randomly spaced array

This function will build an array of integers that is in sorted order but with random increment between items. It takes two arguments, the number of integers in the array to be returns and the max distance between consecutive numbers in the array.

    method increasingArray:  takes two parameters given next
                             returns an arraylist of increasing integers
    PARAM: count: the size of the array list to be returned
            sepr: the max separation between consecutive items
    Let: rtn = empty arraylist of integers
         rand = new Random()  // create an instance of the Java class Random
         curr = 0
         while count>0 
             add curr to rtn
             nr= rand.nextInt(sepr) 
             curr = curr + nr
             decrement count 
         return rtn

Test

In your main, write code to do at least the following:

  use increasingArray to make a list of 20 items with a max   
       separation of 10 
  Use increasingArray to make a list of 50 items with a max
       separation of 5
  Merge the two lists
  Print all of the values in each of the three lists.

What to hand in

Stop after 80 minutes. Send email containing your code to gtowell@brynmawr.edu.