sorting prove that the worst-case running time of this algorithm is ( log nc conduct experiments to determine how often heapsort gets called implement this technique in conjunction with tail-recursion removal in exercise explain why the technique in exercise would no longer be needed when implementing quicksortif the array contains lots of duplicatesit may be better to perform three-way partition (into elements less thanequal toand greater than the pivotto make smaller recursive calls assume three-way comparisons give an algorithm that performs three-way in-place partition of an -element subarray using only three-way comparisons if there are items equal to the pivotyou may use additional comparable swapsabove and beyond the two-way partitioning algorithm (hintas and move toward each othermaintain five groups of elements as shown below)equal small unknown large equal prove that using the algorithm abovesorting an -element array that contains only different valuestakes (dntime write program to implement the selection algorithm solve the following recurrencet( ( / ) - = ( )cnt( sorting algorithm is stable if elements with equal elements are left in the same order as they occur in the input which of the sorting algorithms in this are stable and which are notwhy suppose you are given sorted list of elements followed by (nrandomly ordered elements how would you sort the entire list if (no( ) (no(log ) (non) how large can (nbe for the entire list still to be sortable in (ntime prove that any algorithm that finds an element in sorted list of elements requires (log ncomparisons using stirling' formulan( / ) pngive precise estimate for log( ! in how many ways can two sorted arrays of elements be mergedb give nontrivial lower bound on the number of comparisons required to merge two sorted lists of elements by taking the logarithm of your answer in part ( prove that merging two sorted arrays of items requires at least comparisons you must show that if two elements in the merged list are consecutive and from different liststhen they must be compared consider the following algorithm for sorting six numbersr sort the first three numbers using algorithm sort the second three numbers using algorithm merge the two sorted groups using algorithm