In this tutorial, we are going to learn about shell sort in detail and its algorithmic implementation.

Shell Sort

• In-place algorithm.

• Difficult to nail down the time complexity because it depends on the gap.

  • Worst Case: O(n^2), but it can perform much better than that.
• Doesn’t require much shifting as insertion sort, So it usually performs better.
• Unstable algorithm.
• Most of the sorting algorithms have a run time complexity of O(N2).
• No sorting algorithm can have time complexity less than O(N).
• Donald Shell discovered the Shell sort.
• Shell Sort improves the efficiency and decreases the run time complexity to O(N^1.25).

• The algorithms for shell sort can be defined in two steps

  • Step 1: divide the original list into smaller lists.
  • Step 2: sort individual sub lists using any known sorting algorithm (like bubble sort, insertion sort, selection sort, etc)

Shell Sort Algorithm

1. Initialize the value of h
2. Divide the list into smaller sub-list of equal interval h
3. Sort these sub-lists using insertion sort
4. Repeat until complete list is sorted

Insertion Sort Programmatic Implementation in Java

public class ShellSort {
	public static void main(String[] args) {

		int[] intArray = { 20, 35, -15, 7, 55, 1, -22 };

		for (int gap = intArray.length / 2; gap > 0; gap /= 2) {
			for (int i = gap; i < intArray.length; i++) {
				int newElement = intArray[i];
				int j = i;
				while (j >= gap && intArray[j - gap] > newElement) {
					intArray[j] = intArray[j - gap];
					j -= gap;
				}
				intArray[j] = newElement;
			}
		}

		for (int i = 0; i < intArray.length; i++) {
			System.out.print(intArray[i]+ " ");
		}
	}
}

Output:

-22 -15 1 7 20 35 55 

Shell Sort (Dividing the List)

• Choose a value K, which is known as increment.
• Based on the value of K, split the list into K sub lists.\ Example: if our original list is x[0], x[1], x[2], x[4]….x[99] and we choose 5 as the value for increment, K then we get the following sub lists.
  * firstlist = x[0], x[5], x[10], x[15]…….x[95]
  * secondlist =x[1], x[6], x[11], x[16]…..x[96]
  * thirdlist =x[2], x[7], x[12], x[17]…….x[97]
  * forthlist =x[3], x[8], x[13], x[18]…….x[98]
  * fifth_list =x[4], x[9], x[14], x[19] …….x[99]
• So the ith sub list will contain every Kth element of the original list starting from index i-1.

Selecting K

• If we use the same value of K, we will get the same sub lists and every time we will sort the same sub lists, which will not result in the ordered final list.
• Sorting the five sub lists independently do not ensure that the full list is sorted!
• So we need to change the value of K (increase or decrease?) for every iteration.

• Donald Shell suggested

  • Which give the increment series as: N/2, N/4, …….1
• Hibbard suggested the sequence of increment as

• Knuth suggested

  • Which gives the increment series as 1, 4, 13….. ht

How many Iterations?

• Number of sub lists are equal to the value of K.
• So we will have to reduce the value of K after every iteration until K will become 1 (we will have only one sub list).
• Hence we know the termination condition for our algorithm is K = 1.
• Since for every iteration we are decreasing the value of the increment (K) the algorithm is also known as “Diminishing Increment Sort”.