Implement both a linked list-based version of Mergesort and an array-based version of Mergesort.

1. Generate a list of 1000 or more elements to be sorted. a. Generating a list in reverse order produces the worst case.

2. Compare the running times of the two versions. a. Save the time in ms before the start of the sort, and, save the time at the end of the sort. Be sure not to include the time for generating the list and the time to display the sorted list. Take the difference between to the times to determine the running time.

3. What can you say about the space requirements of each?

Pseudocode for one version of a List input to mergesort follows:

List mergesort(List inlist)

{

if (inlist.length() <= 1) return inlist;;

List L1 = half of the items from inlist;

List L2 = other half of the items from inlist;

return merge(mergesort(L1), mergesort(L2));

}

static >

void mergesort(E[] A, E[] temp, int l, int r)

{

int i, j, k, mid = (l+r)/2; // Select the midpoint

if (l == r)

return; // List has one element

if ((mid-l) >= THRESHOLD)

mergesort(A, temp, l, mid);

else

inssort(A, l, mid-l+1);

if ((r-mid) > THRESHOLD)

mergesort(A, temp, mid+1, r);

else

inssort(A, mid+1, r-mid);

// Do the merge operation. First, copy 2 halves to temp.

for (i=l; i<=mid; i++)

temp[i] = A[i];

for (j=1; j<=r-mid; j++)

temp[r-j+1] = A[j+mid];

// Merge sublists back to array

for (i=l,j=r,k=l; k<=r; k++)

if (temp[i].compareTo(temp[j])<0)

A[k] = temp[i++];

else

A[k] = temp[j--];

}