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); } }