figure complete -sort after the complete -sortthe array can be thought of as comprising four subarrays( , , )( , , )( , )and ( , )each of which is completely sorted these subarrays are interleavedbut otherwise independent notice thatin this particular exampleat the end of the -sort no item is more than cells from where it would be if the array were completely sorted this is what is meant by an array being "almostsorted and is the secret of the shellsort by creating interleavedinternally sorted sets of itemswe minimize the amount of work that must be done to complete the sort nowas we noted in the insertion sort is very efficient when operating on an array that' almost sorted if it only needs to move items one or two cells to sort the fileit can operate in almost (ntime thus after the array has been -sortedwe can -sort it using the ordinary insertion sort the combination of the -sort and the -sort is much faster than simply applying the ordinary insertion sort without the preliminary -sort diminishing gaps we've shown an initial interval--or gap--of cells for sorting -cell array for larger arrays the gap should start out much larger the interval is then repeatedly reduced until it becomes for instancean array of , items might be -sortedthen -sortedthen sortedthen -sortedthen -sortedand finally -sorted the sequence of numbers used to generate the intervals (in this example is called the interval sequence or gap sequence the particular interval sequence shown hereattributed to knuth (see the bibliography)is popular one in reversed formstarting from it' generated by the recursive expression * where the initial value of is the first two columns of table show how this formula generates the sequence table knuth' interval sequence