dec( ) [ : [ ]sift( - ) [ :xif mh then sift(lm- endif then (*heap fullstart new run* : end endfiles readint(rxend(*step flush lower half of heap* :mrepeat dec( )files writeint(wh[ ]) [ : [ ]sift( - )dec( ) [ : [ ]if mh then sift(lr- end until (*step flush upper half of heapstart new run*while do files writeint(wh[ ]) [ : [ ]dec( )sift( rendreturn dest end distribute analysis and conclusions what performance can be expected from polyphase sort with initial distribution of runs by heapsortwe first discuss the improvement to be expected by introducing the heap in sequence with randomly distributed keys the expected average length of runs is what is this length after the sequence has been funnelled through heap of size mone is inclined to say mbutfortunatelythe actual result of probabilistic analysis is much betternamely (see knuthvol thereforethe expected improvement factor is an estimate of the performance of polyphase can be gathered from table indicating the maximal number of initial runs that can be sorted in given number of partial passes (levelswith given number of sequences as an examplewith six sequences and heap of size file with up to ' ' initial runs can be sorted within partial passes this is remarkable performance reviewing again the combination of polyphase and heapsortone cannot help but be amazed at the complexity of this program after allit performs the same easily defined task of permuting set of items as is done by any of the short programs based on the straight array sorting principles the moral of the entire may be taken as an exhibition of the following the intimate connection between algorithm and underlying data structureand in particular the influence of the latter on the former the sophistication by which the performance of program can be improvedeven when the available structure for its data (sequence instead of arrayis rather ill-suited for the task exercises which of the algorithms given for straight insertionbinary insertionstraight selectionbubble sortshakersortshellsortheapsortquicksortand straight mergesort are stable sorting methods would the algorithm for binary insertion still work correctly if were replaced by < in the while clausewould it still be correct if the statement : + were simplified to :mif notfind sets of values an- upon which the altered program would fail program and measure the execution time of the three straight sorting methods on your computer