while do : [ ] [ : [ ] [ :xdec( )sift(lrend end heapsort analysis of heapsort at first sight it is not evident that this method of sorting provides good results after allthe large items are first sifted to the left before finally being deposited at the far right indeedthe procedure is not recommended for small numbers of itemssuch as shown in the example howeverfor large nheapsort is very efficientand the larger isthe better it becomes -even compared to shellsort in the worst casethere are / sift steps necessarysifting items through log( / )log( / + )log( - positionswhere the logarithm (to the base is truncated to the next lower integer subsequentlythe sorting phase takes - siftswith at most log( - )log( - ) moves in additionthere are - moves for stashing the item from the top away at the right this argument shows that heapsort takes of the order of log(nmoves even in the worst possible case this excellent worst-case performance is one of the strongest qualities of heapsort it is not at all clear in which case the worst (or the bestperformance can be expected but generally heapsort seems to like initial sequences in which the items are more or less sorted in the inverse orderand therefore it displays an unnatural behavior the heap creation phase requires zero moves if the inverse order is present the average number of moves is approximately / log( )and the deviations from this value are relatively small partition sort after having discussed two advanced sorting methods based on the principles of insertion and selectionwe introduce third improved method based on the principle of exchange in view of the fact that bubblesort was on the average the least effective of the three straight sorting algorithmsa relatively significant improvement factor should be expected stillit comes as surprise that the improvement based on exchanges to be discussed subsequently yields the best sorting method on arrays known so far its performance is so spectacular that its inventorc hoarecalled it quicksort [ and quicksort is based on the recognition that exchanges should preferably be performed over large distances in order to be most effective assume that items are given in reverse order of their keys it is possible to sort them by performing only / exchangesfirst taking the leftmost and the rightmost and gradually progressing inward from both sides naturallythis is possible only if we know that their order is exactly inverse but something might still be learned from this example let us try the following algorithmpick any item at random (and call it )scan the array from the left until an item ai is found and then scan from the right until an item aj is found now exchange the two items and continue this scan and swap process until the two scans meet somewhere in the middle of the array the result is that the array is now partitioned into left part with keys less than (or equal toxand right part with keys greater than (or equal tox this partitioning process is now formulated in the form of procedure note that the relations and and <=whose negations in the while clause are with this change acts as sentinel for both scans procedure partitionvar ijintegerwxitembegin : : - select an item at randomrepeat while [ix do : + end