advanced sorting the worst-case performance is not significantly worse than the average performance (we'll see later in this that the worst-case performance for quicksort can be much worse unless precautions are taken some experts (see sedgewick in appendix "further reading"recommend starting with shellsort for almost any sorting project and changing to more advanced sortlike quicksortonly if shellsort proves too slow in practice insertion sorttoo many copies because shellsort is based on the insertion sortyou might want to review the section titled "insertion sortin recall that partway through the insertion sort the items to the left of marker are internally sorted (sorted among themselvesand items to the right are not the algorithm removes the item at the marker and stores it in temporary variable thenbeginning with the item to the left of the newly vacated cellit shifts the sorted items right one cell at timeuntil the item in the temporary variable can be reinserted in sorted order here' the problem with the insertion sort suppose small item is on the far rightwhere the large items should be to move this small item to its proper place on the leftall the intervening items (between the place where it is and where it should bemust be shifted one space right this step takes close to copiesjust for one item not all the items must be moved full spacesbut the average item must be moved / spaceswhich takes times / shifts for total of / copies thusthe performance of insertion sort is ( this performance could be improved if we could somehow move smaller item many spaces to the left without shifting all the intermediate items individually -sorting the shellsort achieves these large shifts by insertion-sorting widely spaced elements after they are sortedit sorts somewhat less widely spaced elementsand so on the spacing between elements for these sorts is called the increment and is traditionally represented by the letter figure shows the first step in the process of sorting -element array with an increment of here the elements and are sorted after and are sortedthe algorithm shifts over one cell and sorts and this process continues until all the elements have been -sortedwhich means that all items spaced four cells apart are sorted among themselves the process is shown (using more compact visual metaphorin figure after the complete -sortthe array can be thought of as comprising four subarrays( , , )( , , )( , )and ( , )each of which is completely sorted these subarrays are interleaved but otherwise independent