sorting prove that comparisons are required to sort elements using any comparisonbased algorithm give an algorithm to sort elements with comparisons write an efficient version of shellsort and compare performance when the following increment sequences are useda shell' original sequence hibbard' increments knuth' incrementshi ( hk+ and hk (with if gonnet' incrementsht sedgewick' increments implement an optimized version of quicksort and experiment with combinations of the followinga pivotfirst elementmiddle elementrandom elementmedian of threemedian of five cutoff values from to write routine that reads in two alphabetized files and merges them togetherforming thirdalphabetizedfile suppose we implement the median-of-three routine as followsfind the median of [left] [center] [right]and swap it with [rightproceed with the normal partitioning step starting at left and at right- (instead of left+ and right- suppose the input is for this inputwhat is the running time of this version of quicksortb suppose the input is in reverse order for this inputwhat is the running time of this version of quicksortprove that any comparison-based sorting algorithm requires ( log ncomparisons on average we are given an array that contains numbers we want to determine if there are two numbers whose sum equals given number for instanceif the input is and is then the answer is yes ( and number may be used twice do the followinga give an ( algorithm to solve this problem give an ( log nalgorithm to solve this problem (hintsort the items first after that is doneyou can solve the problem in linear time code both solutions and compare the running times of your algorithms repeat exercise for four numbers try to design an ( log nalgorithm (hintcompute all possible sums of two elements sort these possible sums then proceed as in exercise repeat exercise for three numbers try to design an ( algorithm consider the following strategy for percolatedownwe have hole at node the normal routine is to compare ' children and then move the child up to if it is larger (in the case of (max)heapthan the element we are trying to placethereby pushing the hole downwe stop when it is safe to place the new element in the hole the alternative strategy is to move elements up and the hole down as far as