give an example input list that requires merge-sort and heap-sort to take (nlogntime to sortbut insertion-sort runs in (ntime what if you reverse this listr- describein pseudo-codehow to perform path compression on path of length in (htime in tree-based partition union/find structure - george claims he has fast way to do path compression in partition structurestarting at node he puts into list land starts following parent pointers each time he encounters new nodeuhe adds to and updates the parent pointer of each node in to point to ' parent show that george' algorithm runs in ( time on path of length - describe an in-place version of the quick-select algorithm in pseudo-code - show that the worst-case running time of quick-select on an -element sequence is ( creativity - linda claims to have an algorithm that takes an input sequence and produces an output sequence that is sorting of the elements in give an algorithmissortedfor testing in (ntime if is sorted explain why the algorithm issorted is not sufficient to prove particular output to linda' algorithm is sorting of