notes after sorting the sub liststhe resulting list we get is as follows - you nowreduce the increment value to and get the following sub lists after sorting these sub liststhe resulting list is as follows - you further reduce increment value to which is our last increment value now there is only one listwhich after sortingwe get- now try to understand and analyse what is happeninghow the elements are movedwe can seeafter the first iteration when the increment was the element - of the listwhich was at th position in the original list has reached to the nd position the element was at th position and has reached the rd position using insertion sort on the whole listwe know that if - has to reach from the th position to the nd positionthe required number of movements of the elements in the list will be very high shell sort performs better than insertion sort by reducing the number of movements of elements in the lists this is achieved by large strides the element take in the beginning cycle upper bound theoremwith the -sequence shellsort needs (nnsteps for sorting sequence of length (papernov/stasevic [ps ]prooflet ht be the closest to we analyze the behavior of shellsort separately for the elements hk with let < since hk we have the conditions mentioned above that hk+ and hk+ are relatively prime and in (hkthereforeo(nhksorting steps suffice for hk-sorting the data sequence since lovely professional university