First download these files:
Your next step is to start insertion sort on an array of 1 million elements. Go to a terminal window and change the directory to where you have loaded these files. Type in javac InsertionSort.java to compile the code and java InsertionSort to start the sort.
Now, see if you can complete merge sort and run it on 1 million elements before the insertion sort ends. You have to write the methods merge and split. Important: each method must be O(n) running time!
You can test your merge sort on 100 elements with MergeSort.testSort. Once it works, run it on 1 million by using the merge sort main method: java MergeSort.