Java: ShellSort

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

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.