Introduction

Shell Sort is an in-place comparison sort that generalizes insertion sort by allowing the exchange of items that are far apart. It improves the efficiency of insertion sort by breaking the original list into smaller sublists, each sorted using insertion sort, and then gradually reducing the gap between elements being compared. This allows elements to move faster toward their sorted position.

How Shell Sort Works

Shell Sort starts by sorting elements far apart from each other and progressively reduces the interval between the elements to be sorted. The idea is that the array becomes “more sorted” after each pass, which means the final insertion sort (with a gap of 1) is much faster.

The algorithm typically uses a gap sequence, which determines the spacing between elements in each pass. One common sequence is to start with n/2, then reduce the gap by half each time until it becomes 1.

Steps of the Shell Sort Algorithm

1. Choose an initial gap size, usually n / 2, where n is the number of elements.
2. Perform a gapped insertion sort for this gap size.
3. Reduce the gap and repeat the process.
4. Continue until the gap is 1, at which point a final insertion sort ensures the array is fully sorted.

Java Example of Shell Sort

Below is an implementation of Shell Sort in Java. It uses a simple gap sequence where the gap is halved in each iteration.

	@Test
	public void ShellSortTest() throws Exception {
        int[] arrToBeSorted = {55, 66, 88, 99, 677, 55, 25, 77};
        sort(arrToBeSorted);
		for (int elem : arrToBeSorted) {
			System.out.println(elem + " ");
		}
	}

    private void sort(int[] values) {
        int n = values.length;
        for (int gap = initialGap(n); gap > 0; gap = nextGap(gap)) {
            applyGapSort(values, gap);
        }
    }

    private static int initialGap(int size) {
        return size / 2;
    }

    private int nextGap(int currentGap) {
        return currentGap / 2;
    }

    private void applyGapSort(int[] data, int gap) {
        for (int i = gap; i < data.length; i++) {
            int insertValue = data[i];
            int mover = i;

            while (mover >= gap && data[mover - gap] > insertValue) {
                data[mover] = data[mover - gap];
                mover -= gap;
            }

            data[mover] = insertValue;
        }
    }

Time Complexity

The performance of Shell Sort depends on the gap sequence. With the basic sequence of halving the gap, the worst-case time complexity is generally O(n²). However, with more sophisticated sequences like the Tokuda or Sedgewick sequences, the time complexity can approach O(n log² n) or better in practice.

Conclusion

Shell Sort is an efficient algorithm for medium-sized datasets and offers better performance than simple algorithms like bubble sort or insertion sort. Its main advantage lies in its ability to move elements over long distances, helping elements get to their correct position faster than insertion sort alone.

You can find the example code on Github.