and find coefficients by which the factors and have to be multiplied to yield real time estimates specifty invariants for the repetitions in the three straight sorting algorithms consider the following "obviousversion of the procedure partition and find sets of values an- for which this version fails : : - : [ div ]repeat while [ix do : + endwhile [jdo : - endw : [ ] [ : [ ] [ : until write procedure that combines the quicksort and bubblesort algorithms as followsuse quicksort to obtain (unsortedpartitions of length ( )then use bubblesort to complete the task note that the latter may sweep over the entire array of elementshenceminimizing the bookkeeping effort find that value of which minimizes the total sort time noteclearlythe optimum value of will be quite small it may therefore pay to let the bubblesort sweep exactly - times over the array instead of including last pass establishing the fact that no further exchange is necessary perform the same experiment as in exercise with straight selection sort instead of bubblesort naturallythe selection sort cannot sweep over the whole arraythereforethe expected amount of index handling is somewhat greater write recursive quicksort algorithm according to the recipe that the sorting of the shorter partition should be tackled before the sorting of the longer partition perform the former task by an iterative statementthe latter by recursive call (henceyour sort procedure will contain only one recursive call instead of two find permutation of the keys for which quicksort displays its worst (bestbehavior ( construct natural merge program similar to the straight mergeoperating on double length array from both ends inwardcompare its performance with that of the procedure given in this text note that in (two-waynatural merge we do not blindly select the least value among the available keys insteadupon encountering the end of runthe tail of the other run is simply copied onto the output sequence for examplemerging of results in the sequence instead of which seems to be better ordered what is the reason for this strategy sorting method similar to the polyphase is the so-called cascade merge sort [ and it uses different merge pattern givenfor instancesix sequences the cascade mergealso starting with "perfect distributionof runs on performs five-way merge from onto until is emptythen (without involving four-way merge onto then three-way merge onto two-way merge onto and finally copy operation from onto the next pass operates in