[ + : else [ + : [ ] [ : end end end end shellsort analysis of shellsort the analysis of this algorithm poses some very difficult mathematical problemsmany of which have not yet been solved in particularit is not known which choice of increments yields the best results one surprising facthoweveris that they should not be multiples of each other this will avoid the phenomenon evident from the example given above in which each sorting pass combines two chains that before had no interaction whatsoever it is indeed desirable that interaction between various chains takes place as often as possibleand the following theorem holdsif -sorted sequence is -sortedthen it remains -sorted knuth [ indicates evidence that reasonable choice of increments is the sequence (written in reverse order where hk- hk+ ht and log ( he also recommends the sequence where hk- hk + ht and log ( for the latter choicemathematical analysis yields an effort proportional to required for sorting items with the shellsort algorithm although this is significant improvement over we will not expound further on this methodsince even better algorithms are known tree sort the method of sorting by straight selection is based on the repeated selection of the least key among itemsthen among the remaining - itemsetc clearlyfinding the least key among items requires - comparisonsfinding it among - items needs - comparisonsetc and the sum of the first - integers is ( - )/ so how can this selection sort possibly be improvedit can be improved only by retaining from each scan more information than just the identification of the single least item for instancewith / comparisons it is possible to determine the smaller key of each pair of itemswith another / comparisons the smaller of each pair of such smaller keys can be selectedand so on with only - comparisonswe can construct selection tree as shown in fig and identify the root as the desired least key [ fig repeated selection among two keys the second step now consists of descending down along the path marked by the least key and eliminating it by successively replacing it by either an empty hole at the bottomor by the item at the alternative branch at intermediate nodes (see figs and againthe item emerging at the root of the tree has the (now secondsmallest key and can be eliminated after such selection stepsthe tree is empty ( full of holes)and the sorting process is terminated it should be noted that each of the