by BehindJava
Data Structures  Shell Sort Algorithm
In this tutorial, we are going to learn about shell sort in detail and its algorithmic implementation.
Shell Sort
 Inplace 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
 Initialize the value of h
 Divide the list into smaller sublist of equal interval h
 Sort these sublists using insertion sort
 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 i1.
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.

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

 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”.