previous theorem although this bound holds for the other incrementsit is too large to be useful intuitivelywe must take advantage of the fact that this increment sequence is special what we need to show is that for any element [pin position pwhen it is time to perform an hk -sortthere are only few elements to the left of position that are larger than [pwhen we come to hk -sort the input arraywe know that it has already been hk+ and hk+ -sorted prior to the hk -sortconsider elements in positions and ii < if is multiple of hk+ or hk+ then clearly [ ia[pwe can say morehowever if is expressible as linear combination (in nonnegative integersof hk+ and hk+ then [ ia[pas an examplewhen we come to -sortthe file is already and -sorted is expressible as linear combination of and because thusa[ cannot be larger than [ because [ < [ < [ < [ < [ nowhk+ hk+ so hk+ and hk+ cannot share common factor in this caseit is possible to show that all integers that are at least as large as (hk+ )(hk+ hk can be expressed as linear combination of hk+ and hk+ (see the reference at the end of the this tells us that the body of the innermost for loop can be executed at most hk (hk times for each of the hk positions this gives bound of (nhk per pass using the fact that about half the increments satisfy hk nand assuming that is eventhe total running time is then / / nhk /hk hk /hk = = / + = = / + because both sums are geometric seriesand since ht/  )this simplifies to ( / nht/ ht/ the average-case running time of shellsortusing hibbard' incrementsis thought to be ( / )based on simulationsbut nobody has been able to prove this pratt has shown that the ( / bound applies to wide range of increment sequences sedgewick has proposed several increment sequences that give an ( / worstcase running time (also achievablethe average running time is conjectured to be ( / for these increment sequences empirical studies show that these sequences perform significantly better in practice than hibbard' the best of these is the sequence { }in which the terms are either of the form or this is most easily implemented by placing these values in an array this increment sequence is the best known in practicealthough there is lingering possibility that some increment sequence might exist that could give significant improvement in the running time of shellsort there are several other results on shellsort that (generallyrequire difficult theorems from number theory and combinatorics and are mainly of theoretical interest shellsort is fine example of very simple algorithm with an extremely complex analysis