Program:

Write a function COMPVEC(X, Y, `) that compares two vectors of integers of length `. (Recall that for two such vectors X and Y of length `, X Y if and only if there exists and index i {0, . . . , ` 1} such that X[j] = Y [j], for j = 0, . . . , i 1 and X[i] < Y [i].)

Implement the following three sorting algorithms on input that consists of n vectors of integers of length ` using the function COMPVEC(X, Y, `) to perform all comparisons between such vectors. 1. Mergesort, 2. Heapsort, 3. Quicksort.

Count the number of key comparisons by counting the calls to COMPVEC(X, Y, `). Count the total running time by using the built-in clock function The input instances:

1. Generate n = 100 randomly ordered vectors of integers between 0 and 99 of length ` = 5

2. Run each of the algorithms on the n generated vectors

3. Run each of the algorithms on the sorted vectors (output of previous step)

4. Run each of the algorithms on the reverse sorted vectors

5. Generate n = 2(to the power 10) = 1, 024 randomly ordered vectors of integers between 0 and 99 of length ` = 3 and run each of the algorithms on the n generated vectors

6. Repeat the previous step for n = 2(to the power 15)= 32, 768 and 2(to the power 20) = 1, 048, 576

Analysis:

Tabulate the performance results, listing both the number of comparisons and the measured clock times.

Use the tabulated number of comparisons on the random instances to determine (approximately) the time complexity and the constant factor. Do the running times correspond to the average-case time complexities?