This is from the book DATA STRUCTURES USING C AND C++ second edition by Langsam, Augenstein, and Tenenbaum:
1. Bubble Sort: least efficient.
x= array of integers
sorting 1 to n
pass through the file sequentially several times, comparing each element with its successor and interchanging if they are in the wrong order
2. Indentation Sort. did not find. Ask if it is the same as n insertion sort.
3. Shell Sort(or diminishing increment sort):sorts several subfiles of the original file, each containing a Kth element of the original file. K is called increment and there is x[k] from 0 to n.
for two successive files i and j, x[(i-1)*k+j-1]. After the first k subfiles are sorted (usually by insertion) a smaller k is chosen. and shell sorted again. ...
.
.
.
ex:
first iteration: k=5
(x[0],x[5])
(x[1],x[6])
(x[2],x[7])
(x[3])
(x[4])
second iteration: k=3
(x[0],x[3],x[6])
(x[1],x[4],x[7])
(x[2],x[5])
third iteration:k=1
(x[0],x[1],...,x[n=7])
c/c++ code:
void shellsort(int x[], int n, int incrmnts[], int numinc)
{
int incr,j,k,span,y;
for(incr=0;incr<numinc;incr++){
/*span is size of increment*/
span=incrmnts[incr];
for (j=span;j<n;j++){
/*insert element x[j] into its proper position within its subfile*/
y=x[j];
for (k=j-span;k>=0 && y<x[k];k -= span)
x[k+span]=x[k];
x[k+span]=y;
}
}
}
recommended for moderately sized files of several undred elements.