Penultimate batch of problems.

A. Mergesort problems

1. Write a method that takes an array of length 100,000 and puts in random numbers between 0 and 100,000 into each element of the array. (Repetition of elements is fine.)

2. Modify mergesort so that, given the above array, you will have 100 elements sorted in ascending order. (It doesn't matter which 100 elements you choose, and you do not need to sort the rest of the array. Just have 100 elements sorted.)

3. What is the order of growth for your algorithm?

4. Is this faster or slower than using insertionsort for finding 100 sorted elements in an array? How do you know?