Java: write a quicksort and merge sort program, follow parameters below: a quicksort (or partition exchange sort) divides the data into 2 partitions separated by a pivot. the first partition contains all the items which are smaller than the pivot. the remaining items are in the other partition. you will write four versions of quicksort: __ select the first item of the partition as the pivot. treat partitions of size one and two as stopping select the first item of the partition as the pivot. treat a partition of size 100 as a stopping case. use an insertion sort to select the first item of the partition as the pivot. treat a partition of size 50 as a stopping case. use an insertion sort to select the median-of-three as the pivot. treat partitions of size one and two as stopping cases. merge sort is a useful sort to know if you are doing external sorting. the need for this will increase as data sizes increase. the traditional merge sort requires double space. to eliminate this issue, you are to implement natural merge using a linked implementation. in your analysis be sure to compare to the effect of using a straight merge sort instead. create input files of four sizes: 50, 1000, 2000, 5000 and 1 integers. for each size file make 3 versions. on the first use a randomly ordered data set. on the second use the integers in reverse order. on the third use the integers in normal ascending order. (you may use a random number generator to create the randomly ordered file, but it is important to limit the duplicates to < 1%. alternatively, you may write a shuffle function to randomize one of your ordered files.) this means you have an input set of 15 files plus whatever you deem necessary and reasonable. the size 50 files are to be turned in. the other sizes are for timing purposes. your code needs to print out the sorted values. files are available at on the course web page if you want to copy them. your data should be formatted so that each number is on a separate line with no leading blanks. there should be no blank lines in the file. each sort must be run against all the input files. with five sorts and 15 input sets, you will have 75 required runs. for grading purposes, for each sort, turn in output only for the size 50 files. you will have 15 sets of output to turn in for the size 50 files. your program should access the system clock to get some time values for the different runs. the call to the clock should be placed as close as possible to the beginning and the end of each sort. if other code is included, it may have a large, albeit fixed, cost, which would tend to drown out the differences between the runs, if any. why take a chance! if you get too many zero time data values or any negative time values then you must fix the problem. one way to do this is to use larger, files than those specified. another solution is to perform the sorting in a loop, n times, and calculate an average value. you would need to be careful to start over with unsorted data, each time through the loop. enter file names as command line prompts. do not use gui/console input.