Invented by D. Shell, it was the fastest known sort before quicksort was invented. A generalization of insertion sort. Lots of research has gone in finding the optimum intervals of the sequence of separations, and trying to find upper bounds of its complexity. For shellsort2, complexity is considered to be O(n^(3/2)) in the worst case.
class ShellSort extends AlgoTri {
ShellSort (int t, VueTris v) { super("Shell Sort", t, v);
}
void insertionsort (int offset, int n, int incr) {
for (int i = incr; i < n; i+= incr)
for (int j = i; (j >= incr)
&& compare(j+offset, j+offset-incr)<
0; j-=incr)
exchange(j+offset,
j+offset-incr);
}
public void sort () {
// here, we use the simplest increment suite.
for (int i = (size/2); i > 1; i /= 2)
for (int j = 0; j < i; j++)
insertionsort(j,
size-j, i);
insertionsort(0, size, 1);
}
};
class ShellSort2 extends AlgoTri {
ShellSort2 (int t, VueTris v) { super("Shell Sort2", t, v);
}
void insertionsort (int offset, int n, int incr) {
for (int i = incr; i < n; i+= incr)
for (int j = i; (j >= incr)
&& compare(j+offset, j+offset-incr)<
0; j-=incr)
exchange(j+offset,
j+offset-incr);
}
public void sort () {
// here, we use a smarter increment suite: n(i) = 3 n(i-1)
+ 1
int maxi=1;
while(maxi < size - 1)
maxi=3*maxi+1;
for (int i = maxi/3; i > 1; i /= 3)
for (int j = 0; j < i; j++)
insertionsort(j,
size-j, i);
insertionsort(0, size, 1);
}
};
Understanding better shell sort is a whole research area. Some variants using bubble sort instead of insertion sort to sort the sub arrays have been proposed (these are called brick sort). Here is a recent paper that summarizes the latest advances.