chap internal sorting can stop early this makes the best case performance become ( (because if the list is already sortedthen no iterations will take place on the first passand the sort will stop right theremodify the bubble sort implementation to add this flag and test compare the modified implementation on range of inputs to determine if it does or does not improve performance in practice double insertion sort is variation on insertion sort that works from the middle of the array out at each iterationsome middle portion of the array is sorted on the next iterationtake the two adjacent elements to the sorted portion of the array if they are out of order with respect to each otherthan swap them nowpush the left element toward the right in the array so long as it is greater than the element to its right and push the right element toward the left in the array so long as it is less than the element to its left the algorithm begins by processing the middle two elements of the array if the array is even if the array is oddthen skip processing the middle item and begin with processing the elements to its immediate left and right firstexplain what the cost of double insertion sort will be in comparison to standard insertion sortand why (note that the two elements being processed in the current iterationonce initially swapped to be sorted with with respect to each othercannot cross as they are pushed into sorted position thenimplement double insertion sortbeing careful to properly handle both when the array is odd and when it is even compare its running time in practice against standard insertion sort finallyexplain how this speedup might affect the threshold level and running time for quicksort implementation starting with the java code for quicksort given in this write series of quicksort implementations to test the following optimizations on wide range of input data sizes try these optimizations in various combinations to try and develop the fastest possible quicksort implementation that you can (alook at more values when selecting pivot (bdo not make recursive call to qsort when the list size falls below given thresholdand use insertion sort to complete the sorting process test various values for the threshold size (celiminate recursion by using stack and inline functions write your own collection of sorting programs to implement the algorithms described in this and compare their running times be sure to implement optimized versionstrying to make each program as fast as possible do you get the same relative timings as shown in figure if notwhy do you think this happenedhow do your results compare with those of your