1. Use the merge function to write a sorting algorithm. This has to be in HTML format with some javascript in it The algorithm is as follows:

function newsort(array):

if array length <= 1:

// an array of length 1 is already sorted

return array

else:

// divide the array in half, sort them separately

// and then merge them back together

mid = middle index of array

left = a new array of size mid

right = a new array of size array length mid

copy leftmost elements of array into left

copy rightmost elements of array into right

left = newsort(left)

right = newsort(right)

result = merge(left, right);

return result

2. Verify that the sorting algorithm above actually sorts some data. Then profile the new sorting algorithm and compare it against the other sorting algorithms you have studied. Produce a plot similar to that given in the key points that shows the relationship between the time it takes to sort and the number of elements in the array. The following functions should help you with this problem:

// build an array of random data to sort

function makeRandomArray(size)

{

var result = Array();

while (size > 0)

{

result.push(Math.floor(Math.random()*100000));

--size;

}

return result;

}

// time the sorting algorithm on the given array, in milliseconds

function timeSortingAlgorithm(arr, sortingAlgorithm)

{

var startTime = new Date()

sortingAlgorithm(arr);

var endTime = new Date();

return endTime.getTime() - startTime.getTime();

}