Java data structures and alg.

1. QUESTION 1a

Write a recursive "Merge" method meeting this specification:

Inputs: a sorted list L1 and a sorted list L2.
Outputs: a sorted list that is the merging of L1 and L2, and, the number of
times two list elements were compared during the merging process (call it C).

The recursive Merge method returns the merging of L1 and L2 as its result. Thus, after
executing L1 = Merge(L1,L2,Nc,Njs), L1 contains the result of the merge and the 'other'
list has been destroyed. In other words, at this point, (1) either L2 has been destroyed,
or (2) the old L1 has been destroyed and now L1==L2.

(Note: Nc is the total number of times two list elements were compared during the merging
process. Njs is the total number of join and split operations that were performed during the
merging process. Nc and Njs are output values but not input values. 2005-11-16 12:45:32)

2. QUESTION 1b

Write a method "General_Sort" that meets this specification:

Inputs: a list L, and a method "Cut_In_Two" that meets the specification below
Outputs: L is sorted in increasing order, and the integer C defined as follows:
C is the total number of times two list elements were compared during the
sorting process, including the comparisons made by the Merge and Cut_In_Two
methods.

General_Sort must use the "general sorting strategy" (described in detail in class):

1. Use the procedure Cut_In_Two to divide L into two pieces
2. Recursively sort the two pieces
3. Merge the results (use the function written in Question 1a).

The function Cut_In_Two meets this specification:

Input: a list L1 containing at least two elements.
Outputs: non-empty lists L2 and L3 such that L1 = L2+L3 (concatenation), and the
integer C (the number of times two list elements were compared during the
cut_in_two process)

The method Cut_In_Two should "RANDOMLY" cut the list L1 in two pieces. Thus L1
can be split at "ANY" position (between 1 and lenght(L1)-1), not necessarily in the
middle position.

3. QUESTION 1c

Write a method Merge_Sort that implements the "merge sort algorithm" simply by calling
GeneralSort with an appropriate Cut_In_Two method (which you must also write).
Merge_Sort should return the sorted list and the integer C returned by
GeneralSort.

4. QUESTION 1d

Write a method Insertion_Sort that implements the "insertion sort algorithm" simply by
calling GeneralSort with an appropriate Cut_In_Two method (which you must also write).
Insertion_Sort should return the sorted list and the integer C returned by
GeneralSort.

5. QUESTION 2

Choose five different lengths of lists ranging from small (e.g. 10) to large (as large as
you can and still finish executing in a few minutes), with reasonably-spaced intermediate
values. For instance: 10, 100, 1000, 10000, 100000. The lists must be randomly generated.

For each of these list lengths, run the program written for question 1 five times using a
different random number seed each time. Average the results.

Plot the average number of comparisons (C) for the two sorting algorithms (merge sort and
insertion sort) as a function of the length of the list.

Which algorithm is better for sorting short lists?
Which will be better for sorting extremely long lists?

Justify your answers.

6. QUESTION 3

How would you modify the methods above in order to implements the "quick sort algorithm"
by simply calling General_Sort?