So how fast is the merge sort? Does it depend on the type of array? We saw with some of our previous sorts that it depended on the initial array. For example, an Insertion sort was much faster for a nearly sorted array.

In this exercise, you are given the Sorter class, which contains a static mergeSort method that takes an int array and length as an input. You are also given the SortTester class which has three static methods for creating $3$ different types of arrays.

For this test, create one of the three arrays, then take a start time using System.currentTimeMillis$().$ Next, run the array through the mergeSort method in the Sorter class. Finally, record the end time and print out the results.

Repeat this for the other two array types.

Sample Output

Random Array: $**$ Results Hidden $**$

Almost Sorted Array: $**$ Results Hidden $**$

Reverse Array: $**$ Results Hidden $**$