sorting and selection - let be sequence of elements on which total order relation is defined recall that an inversion in is pair of elements and such that appears before in but describe an algorithm running in ( log ntime for determining the number of inversions in - let be sequence of integers describe method for printing out all the pairs of inversions in in ( ktimewhere is the number of such inversions - let be random permutation of distinct integers argue that the expected running time of insertion-sort on is ( (hintnote that half of the elements ranked in the top half of sorted version of are expected to be in the first half of - let and be two sequences of integers each given an integer mdescribe an ( log )-time algorithm for determining if there is an integer in and an integer in such that - given set of integersdescribe and analyze fast method for finding the log integers closest to the median - bob has set of nuts and set of boltssuch that each nut in has unique matching bolt in unfortunatelythe nuts in all look the sameand the bolts in all look the same as well the only kind of comparison that bob can make is to take nut-bolt pair (ab)such that is in and is in band test it to see if the threads of are largersmalleror perfect match with the threads of describe and analyze an efficient algorithm for bob to match up all of his nuts and bolts - our quick-select implementation can be made more space-efficient by initially computing only the counts for sets leand gcreating only the new subset that will be needed for recursion implement such version - describe an in-place version of the quick-select algorithm in pseudo-codeassuming that you are allowed to modify the order of elements - show how to use deterministic ( )-time selection algorithm to sort sequence of elements in ( log nworst-case time - given an unsorted sequence of comparable elementsand an integer kgive an ( log kexpected-time algorithm for finding the (kelements that have rank /  /  / and so on - space aliens have given us functionalien splitthat can take sequence of integers and partition in (ntime into sequences sk of size at most /keachsuch that the elements in si are less than or equal to every element in si+ for for fixed numberk show how to use alien split to sort in ( log nlog ktime - read documenation of the reverse keyword parameter of python' sorting functionsand describe how the decorate-sort-undecorate paradigm could be used to implement itwithout assuming anything about the key type