Consider the following variation of merge sort where the recursive calls are made only till the list is large; if the list is small, insertion sort is used is used to sort the list.

NewMergeSort(array A)

{

if A has L or fewer elements then InsetionSort(A) else

{

split A into Left and Right;

NewMergeSort(Left); NewMergeSort(Right); Merge Left and Right

}

}

What you have to do in this problem is to see what value of L gives the best results.

1. Consider at least the following values of L: 1, 2, 4, 8, 16, 32, 64.

2. Generate large random arrays (i.e. the values of the arrays are generated using a random number generator)

run NewMergeSort with different values of L and see which value of L yields the fastest result.