This algorithm is a simple extension of Insertion sort. Its speed comes from the fact that it exchanges elements that are far apart (the insertion sort exchanges only adjacent elements).

The idea of the Shell sort is to rearrange the file to give it the property
that taking every *h ^{th}* element (starting anywhere) yields a
sorted file. Such a file is said to be

SHELL_SORT (A)for

h= 1 toh£N/9 do

for (;h> 0;h!= 3) do

fori=h+1 toi£ndo

v=A[i]

j=i

while (j>hANDA[j-h] >v

A[i] =A[j-h]

j=j-h

A[j] =v

i=i+ 1

The function form of the running time for all Shell sort depends on the
increment sequence and is unknown. For the above algorithm, two conjectures are
*n*(log*n*)^{2} and
*n*^{1.25}. Furthermore, the
running time is not sensitive to the initial ordering of the given sequence,
unlike Insertion sort.

Shell sort is the method of choice for many sorting application because it has acceptable running time even for moderately large files and requires only small amount of code that is easy to get working. Having said that, it is worthwhile to replace Shell sort with a sophisticated sort in given sorting problem.

voidshellSort(intnumbers[],intarray_size) {inti, j, increment, temp; increment = 3;while(increment > 0) {for(i=0; i < array_size; i++) { j = i; temp = numbers[i];while((j >= increment) && (numbers[j-increment] > temp)) { numbers[j] = numbers[j - increment]; j = j - increment; } numbers[j] = temp; }if(increment/2 != 0) increment = increment/2;else if(increment == 1) increment = 0;elseincrement = 1; } }