**Due date: **

Late assignments will be penalized 10% per day, and will not be accepted after .

- A disk containing only two files: the source listing and
executable for the program in the assignment.
- Printouts of the program and the output it produces in test data of your own choice.

Name, Student Number, Assignment Number, Course Number (T26)

Assignments which are not in an envelope will not be marked

Deposit your envelope in .

Your program must conform to the programming standards. These are described in a separate sheet.

Note that the main program writes out information about how much memory has been allocated by your procedures but not returned to the global pool. These numbers should always be 0: if they are not, you have bugs to fix.

The program handout consists of 2 files: Partial6.c and Partial6.h. The only file you should modify is Partial6.c. Partial6.h is automatically included and supplies an appropriate testing procedure for questions 1a, 1c, 1d and 2 - there is no testing procedure for question 1b. In order to get appropriate testing procedure for the question you are working on, you must modify accordingly the 2nd macro definition at the top of file Partial6.c. For example, to get the testing procedure for question 1a, it should be:

#define QUESTION1awhereas, for question 2 it should be:

#define QUESTION2

`merge`

meeting this specification:
- Inputs: two lists, L1 and L2.
- Outputs: L1', L2' (i.e. L1 and L2 are changed), and two integers: Nc, Njs
- Preconditions: L1 and L2 are sorted (in increasing order)
- Postconditions: L1' is the result of merging L1 and L2. L2' is
undefined. 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.Your procedure should do as few

`split`

s and`join`

s as possible, and it should not use the`insert`

operation.**Hint:**it is probably simplest to write`merge`

recursively.

- Either L1' is the result of merging L1 and L2, and L2' is
undefined.
- Or (the other way around) L2' is the result of merging L1 and L2, and L1' is undefined.

`merge`

to be a function that returns this result as its
value. 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`

.
`general_sort`

that meets this
specification:
- Inputs: a list, L, and a procedure
`cut_in_two`

that meets the specification below - Outputs: L' (i.e. L is changed), and two integers: Nc, Njs
- Preconditions: L is defined
- Postconditions: L' is sorted in increasing order. Nc 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`

procedures. Njs is the total number of`join`

and`split`

operations that were performed during the sorting process, including the joins and splits done by the`merge`

and`cut_in_two`

procedures.The procedure must use the general sorting strategy (described in detail in class):

- use the procedure
`cut_in_two`

to divide L into two pieces - recursively sort the two pieces
`merge`

the results (use the procedure written in Question 1a).

- use the procedure

`cut_in_two`

meets this specification:
- Input: a list, L1
- Outputs: L1' (i.e. L1 is changed), L2 (a list), and two integers, Nc and Njs
- Preconditions: L1 has 2 or more elements
- Postconditions: neither L1' nor L2 is empty, and collectively
they contain all the elements of L1 (and nothing else). Nc is
the number of times two list elements were compared during the
`cut_in_two`

process. Njs is the total number of`join`

and`split`

operations that were performed during the`cut_in_two`

process.

`merge_sort`

that implements the
mergesort algorithm simply by calling `general_sort`

with
an appropriate `cut_in_two`

procedure (which you must also
write). `merge_sort`

should return the sorted list L' and
the integers Nc and Njs returned by `general_sort`

.
`insertion_sort`

that implements the
insertion sort algorithm simply by calling `general_sort`

with an appropriate `cut_in_two`

procedure (which you must
also write). `insertion_sort`

should return the sorted list
L' and the integers Nc and Njs returned by `general_sort`

.
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 and the average number of splits/joins 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?