Problem
1. Implement a recursive Merge sort with a cutoff to insertion sort for sub files with less than M elements; determine empirically the value of M for which it runs fastest on a random file of 1000 elements.
2. Empirically compare the recursive and non-recursive Merge sorts for linked lists and N = 1000.
3. Implement recursive Merge sort for an array of N integers, using an auxiliary array of size less than N /2.