unsorted sorted figure -sorting and notice thatin this particular exampleat the end of the -sort no item is more than two 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 needs to move items only one or two cells to sort the fileit can operate in almost (ntime thusafter 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 interval 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 here