Decrementing Increment or Just Shell-Sort - Practices

Shell-sorting is a better solution than insertion-sort, but it also contains insertion-sorting. First it splits our unsorted array into groups. In each group are elements whose positions in the array are on equidistant positions.

The number of spaces between elements in groups is called increment h1. Tbe number of groups, naturally, suits the value of increment. Now each group is sorted by insertion-sort method, after that our array is h1-sorted.

In our next step our increment is decremented and its value is h2.  Then we form smaller numbers of groups with more elements per group. Our algorithm ends when our increment reaches value one. This means that now we just use insertion-sort on the whole array, after that our array is completely sorted.
 
Let’s see what this algorithm looks like:


SHELL-SORT:
for i =1 to n do 
inc=h[i]
 for j=inc+1 to n do
  y=a[j]
  k=j-inc
  while ((k>=1) and (y<=a[k])) do
   a[k+inc] = a[k]
   k=k-inc
  end_while
 end_for
end_for



In this algorithm we assume that we have our increments in an array h[1:t]. Notice that everything inside the second for loop is just insertion-sort method used on groups.

It's not obvious that this method has better performances than insertion-sort, but it does. In the beginning our increment h is big so groups are smaller, that means that speed increases on each group using insertion-sort. Each consecutive step our groups are bigger, but now those groups are sorted, facilitating insertion-sort on remaining groups. See step-by-step how this works below: