Please write the program in Java:

2. Quicksort Optimized version of Quicksort Implement an optimized version quicksort algorithm with the following changes: a. Pivot: (i) First element (or any random element) and (ii) median of a[left], a[center], and a[right] of the subarray (or any three random elements in the subarray) b. Cut off to insertion sort for subarrays with less than M elements from 0 to 30. You need to add the following two methods: (i) getPivot(a, lo, hi) method that returns the pivot element based on your chosen strategy in the subarray a[lo..hi] (ii) insertionSort(a, lo, hi) that sorts the subarray a[lo..hi] Empirically determine the value M for which value of quicksort runs fasted in your environment to sort random arrays of N doubles, for N = 103 , 104 , 105 , and 106 . Plot the average running times for M from 0 to 30.