Write the following method for sorting an array of integers( IN JAVA):

recursive quick sort methods:

A modified recursive quick sort method that uses the median-of-three method (pick the median of the 1st, middle and last element of the sub-array as the pivot) to choose the pivot. Also, the base cases for this modified method are lists of 10 elements or less. Your modified method should sort a list of 10 elements or less directly (i.e., with no recursion) using your insertion sort method. Add An error-checking method that makes sure that an array is sorted (by checking that each item (after the first item) is at least as large as the previous item).

Finally, write a main method that reads integers from a file into an array and, with each of the above sorting methods, performs the following steps:

Makes a copy of the input array. Remember to make a separate copy of the array for each sorting call (or else you will be resorting a sorted array!). You can use the System.arraycopy.

Sort a new copy of the array using the sorting method, timing how long the method took (in milliseconds). You can time a method as follows:

import java.util.*; ... long timestamp; ... timestamp = new Date().getTime(); // call your method here timestamp = new Date().getTime() - timestamp; 

Run the error-checking method on the sorted array after you have called the method.

Your output should include the timing of each method, the size of the array sorted and whether the error-checking method found any errors in the output from each method, all with appropriate headers. Thus, your output will look something like the following:

Time for insertion sort: xxxx milliseconds. Insertion sort successfully sorted xxxx elements. Time for the plain merge sort: xxxx milliseconds. Plain quick sort successfully sorted xxxx elements. Time for the plain quick sort(1st element as pivot): xxxx milliseconds. Plain quick sort successfully sorted xxxx elements. Time for the plain quick sort(median of 3 as pivot): xxxx milliseconds. Plain quick sort successfully sorted xxxx elements. The sorting program ended normally. 

(Use the results of your error-checking method to decide whether to print that a sorting method "successfully" or "unsuccessfully" sorted the array.)

Test Data

50 854 540 492 656 345 599 518 325 691 700 6 279 938 937 940 411 949 333 717 992 685 378 652 33 701 66 666 657 232 610 598 342 349 210 828 879 378 216 257 94 957 797 21 909 878 730 711 135 118 259