/*shellsortusing shell' (poorincrements *template void shellsortvector forint gap size gap gap / forint gapi size)++ comparable tmp std::moveai )int iforj >gap &tmp aj gap ] -gap aj std::moveaj gap )aj std::movetmp )figure shellsort routine using shell' increments (better increments are possibleaffect the implementationa careful examination shows that the action of an hk -sort is to perform an insertion sort on hk independent subarrays this observation will be important when we analyze the running time of shellsort popular (but poorchoice for increment sequence is to use the sequence suggested by shellht / and hk hk+ / figure contains function that implements shellsort using this sequence we shall see later that there are increment sequences that give significant improvement in the algorithm' running timeeven minor change can drastically affect performance (exercise the program in figure avoids the explicit use of swaps in the same manner as our implementation of insertion sort worst-case analysis of shellsort although shellsort is simple to codethe analysis of its running time is quite another story the running time of shellsort depends on the choice of increment sequenceand the proofs can be rather involved the average-case analysis of shellsort is long-standing open problemexcept for the most trivial increment sequences we will prove tight worst-case bounds for two particular increment sequences theorem the worst-case running time of shellsort using shell' increments is ( proof the proof requires showing not only an upper bound on the worst-case running time but also showing that there exists some input that actually takes ( time to run