 sorting suppose we exchange elements [iand [ + ]which were originally out of order prove that at least and at most inversions are removed show the result of running shellsort on the input using the increments { what is the running time of shellsort using the two-increment sequence { } show that for any nthere exists three-increment sequence such that shellsort runs in ( / time show that for any nthere exists six-increment sequence such that shellsort runs in ( / time prove that the running time of shellsort is ( using increments of the form cc ci for any integer  prove that for these incrementsthe average running time is ( / prove that if -sorted file is then -sortedit remains -sorted prove that the running time of shellsortusing the increment sequence suggested by hibbardis ( / in the worst case (hintyou can prove the bound by considering the special case of what shellsort does when all elements are either or set [ if is expressible as linear combination of ht ht- / + and otherwise determine the running time of shellsort for sorted input reverse-ordered input do either of the following modifications to the shellsort routine coded in figure affect the worst-case running timea before line subtract one from gap if it is even before line add one to gap if it is even show how heapsort processes the input what is the running time of heapsort for presorted inputshow that there are inputs that force every percolatedown in heapsort to go all the way to leaf (hintwork backward rewrite heapsort so that it sorts only items that are in the range low to highwhich are passed as additional parameters sort using mergesort how would you implement mergesort without using recursion determine the running time of mergesort for sorted input reverse-ordered input random input in the analysis of mergesortconstants have been disregarded prove that the number of comparisons used in the worst case by mergesort is log log