Shell sort is a comparison-based sorting technique in which the elements of a particular distance (or gap) are compared with each other and according to the order of sorting their values are swapped. 

It is different from a bubble or selection sort. It is an in-place sorting algorithm where no extra memory space is required to sort the data. After each pass of sorting the gap is reduced and the sorting continues till the gap between the two elements reaches 0. 

The gap between two elements decreased depending on the sequence used to sort. The original sequence of gapping is n/2, n/4, n/8, ….., 1 where n is the number of elements of the array. There are some other sequences also which can be used to sort the elements. They are:

1. Knuth’s increments: 1, 4, 13, …, (3k – 1) / 2

2. Pratt: 1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, 24, 36, 54, 81....

3. Sedgewick’s increments: 1, 8, 23, 77, 281, 1073, 4193, 16577...4j + 1+ 3·2j + 1.

4. Papernov & Stasevich increment: 1, 3, 5, 9, 17, 33, 65,...

5. Hibbard’s increments: 1, 3, 7, 15, 31, 63, 127, 255, 511…

PROCEDURE WITH EXAMPLE:

Suppose there is an array that has 8 elements as follows:

The array should be sorted in ascending order. In this sorting, the original sequence of gapping is used i.e. n/2 , n/4, n/8, … , 1

So here n=8 (total number of elements)

Pass 1:

For the first pass the gap= n/2 = 8/2 = 4

So, first the first element of the array i.e. 56 is compared with the element at index 4, here the element is 43. As 43 is lesser than 56 so, swapping required and 56 will be stored at index 4 of the array. And as the interval is 4 so no other element is there to compare so 43 will be stored at 0th position and the array will be:

Now, the second gap is n/4 = 8/4 =2 similarly 78 will be compared with 12 and as 12 is lesser than 78 they will also be swapped and the array will be:

Here, between 34 and 69, 34 is already lesser than 69 so there will be no swapping. So the array will remain unchanged.

Now, the last pair i.e. 67 and 54 will be compared and will be swapped and after 1st pass we will get the array:

Pass 2:

In the second pass, the gapping is n/4 = 8/4 = 2

Before the 2nd pass the array is:

First, 43 is compared to 34. As 34 is lesser than 43 so it will be swapped. And the array will be:

12 and 54 will be compared next but as there is no swapping the array will remain same.

This step will be a little different from the previous steps. In this step 56 and 43 will be compared first (i.e. index 4 and index 2) here no change will be performed but again 43 will be compared with 34 (i.e. index 2 with index 0), as 34 is also lesser than 43 so there will be no change. That means all the elements of the array of the same interval from right to left will be compared in a similar way so the array will remain the same.

Here also 78 will be compared to 54 and again 54 will be compared to 12. But as they are incorrect order so there will be no change.

In this step 69 will be compared with 56, 56 will be compared with 43, and 43 will again be compared with 34, all these elements are in the correct order so there will be no change.

Firstly 67 is compared with 78, as 67 is lesser than 78 so it will be swapped. Now 67 will be compared to 54 but as 67 is greater than 54 so there will be no swapping. The 67 will be placed at the position of 78 and the array will be:

Pass 3:

Here the gap is: n/8= 8/8 = 1. So here the adjacent elements will be compared.

Before starting the sorting the array is:

Here, 34 will be compared to 12. As 12 is lesser than 34, it will be swapped. After swapping the array will be:

Here, 43 will be compared to 34, and 34 will be compared to 12. As they are in the correct order so there will be no change.

Here also the array is already in sorted order. Similarly in the next steps, the array elements will be compared by the following steps:

INPUT: An unsorted array a[6,2,4,1,…………….,n]
OUTPUT: An sorted array a[1,2,3,4,5,…………..,n] (in ascending order)
PROCESS:
Step 1: [Taking the inputs from the user]
	Read n
	for i=0 to n repeat
		read arr[i]
Step 2: [Sorting the elements using shell sort]
Set step<-n/2
	While step>0 repeat
		For i=step to n repeat
			Set tmp<-arr[i]
			For j=i to j>=step and  arr[j-step]>tmp repeat 
				Set arr[j]<-arr[j-step]
				Set j<-(j-step)
			Set arr[j]<-tmp
		Set step<-step/2
Step 3: [Displaying the array elements]
	For i=0 to n repeat
		Print arr[i]
Step 4: Stop.