1.

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.

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.

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.

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.

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 intermediatevalues. 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.

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

Attachment:- Sorting_-1 (2).zip