Shell sort in java

Shell sort is in place comparison based sorting algorithm. It is generalization of insertion sort. It was invented by Donald shell.
It allows to sort elements which are far apart. In case of insertion sort, comparison happens between only adjacent elements but in shell sort, it avoid comparing adjacent elements until last steps. Last step of shell sort is ultimately insertion sort.
In short, it improves insertion sort by comparison and exchange elements that are far away.
Shell sort uses a sequence that can be referred as increment sequence. Shell sort makes multiple passes over array and sort number of equally sized array using insertion sort.

Java program to implement shell sort:

When you run above program, you will get below output:

Time complexity:
Best case: O(n)
Average case: Depends on gaps
Worst case : o(nlog2n)

Add Comment