Sort-test improvement. Run empirical studies for large randomly ordered arrays to study th...

Sort-test improvement. Run empirical studies for large randomly ordered arrays to study the effectiveness of the modification described in exercise 2.2.8 for random data. In particular, develop a hypothesis about the average number of times the test (whether an array is sorted) succeeds, as a function of N (the original array size for the sort).

Exercise

Suppose that algorithm is modified to skip the call on merge() whenever a[mid] >= a[mid+1]. Prove that the number of compares used to mergesort a sorted array is linear.

Algorithm Top-down mergesort