subsequentlythree improved methods will be discussednamelyone for each basic sorting methodinsertionselectionand exchange advanced sorting methods insertion sort by diminishing increment refinement of the straight insertion sort was proposed by shell in the method is explained and demonstrated on our standard example of eight items (see table firstall items that are four positions apart are grouped and sorted separately this process is called -sort in this example of eight itemseach group contains exactly two items after this first passthe items are regrouped into groups with items two positions apart and then sorted anew this process is called -sort finallyin third passall items are sorted in an ordinary sort or -sort -sort yields -sort yields -sort yields table an insertion sort with diminishing increments one may at first wonder if the necessity of several sorting passeseach of which involves all itemsdoes not introduce more work than it saves howevereach sorting step over chain either involves relatively few items or the items are already quite well ordered and comparatively few rearrangements are required it is obvious that the method results in an ordered arrayand it is fairly obvious that each pass profits from previous passes (since each -sort combines two groups sorted in the preceding -sortit is also obvious that any sequence of increments is acceptableas long as the last one is unitybecause in the worst case the last pass does all the work it ishowevermuch less obvious that the method of diminishing increments yields even better results with increments other than powers of the procedure is therefore developed without relying on specific sequence of increments the increments are denoted by ht- with the conditions ht- hi+ hi the algorithm is described by the procedure shellsort [ for procedure shellsortconst var ijkmsintegerxitemharray of integerbegin [ : [ : [ : [ : for : to - do : [ ]for : to - do : [ ] : -kwhile ( > ( [ ]do [ + : [ ] : - endif ( >kor ( > [ ]then (adens _sorts *