Out: November 16, 2001 Due: November 30, 2001
Measure the speed of your implementation of Merge Sort versus the implementation of insertion sort.
Using the random data generator, run various tests at various increasing number of elements. The Insertion Sort should show a time dependence on the number of numbers to sort, n, as n squared. Merge sort's depdenence should be like n log n.
Plot the results on log-log paper. Consider the function y(n)= a n^2 on log-log paper, that is, ploting log y against log x:
y = log y(n) = log a + 2 log n
= 2 x + A.
The function y(n)= b n log n should look like:
y = log y(n) = log b + log n + log log n
= x + log x+ B
The overhead is compared by A versus B. We suppose that
B will be larger than A, because Merge Sort is a more complicated
algorithm. But eventually, the x + log x will be smaller than
2x, and for that value of x, Merge Sort will be faster than
Insertion Sort.
Determine the value of n at which MergeSort beats InsertionSort.