Merging CS 151 -- Lab 9, April 7 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 p1N & p2 > M
break
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 gtowell151@cs.brynmawr.edu.
