ShellSort is not a comparison-based sorting algorithm like those previously shown on this blog, it uses the property of InsertionSort that nearly sorted arrays of values are sorted very quickly. It has a performance of O(n log² n) which makes it a lot faster than a lot of other algorithms, certainly the O(n²) ones, but not entirely the fastest.
public static void shellSort(int[] ia) {
int l = ia.length;
if (l == 1)
return;
int inc = l / 2;
while (inc != 0) {
for (int i = inc; i != l; i++) {
int t = ia[i];
int j = i;
while (j >= inc && ia[j - inc] > t) {
ia[j] = ia[j - inc];
j = j - inc;
}
ia[j] = t;
}
inc = (int) (inc / 2.2);
}
}