Shell Sort: Shell sort is a sorting algorithm. It is an extended version of the insertion sort.

• In this sorting, we compare the elements that are distant apart rather than the adjacent.
• We start by comparing elements that are at a certain distance apart. So, if there are N elements then we start with a value gap < N.
• In each iteration we keep decreasing the value of the gap until the difference becomes 1.
• In the last iteration, the shell sort acts as an insertion-type.

### Shell sort example

Suppose you have the following array, which you have to sort.

The size of array is 9, so n = 9.

Now, find the value of the Gap.

Gap = floor(n / 2)

= floor (9 / 2)

= floor(4.5)

= 4

Pass = 1 Gap = 4

Gap 4 means, if we consider the first element at index 0 then next element will be at index 0+4 = 4., and third element will be at index 4 + 4 = 8.

Similarly, if we consider the element at index 1 then next element will be at index 1 + 4 = 5, and third element will be at index 5 + 4 = 9. But there is no 9th index in the above array so we will just have index 1 and 5.

Similarly, if we consider the element at index 2, 3, and 4 respectively then next element will be at index 2 + 4 = 6, 3 + 4 = 7, and 4 + 4 = 8 respectively.

Compare the elements.

A > A = 14 > 23 // false

A > A = 18 > 40 // false

A > A = 19 > 29 // false

A > A = 37 > 30 // true i.e., swap the both element positions.

A > A = 23 > 11 // true i.e., swap the both element positions.

A > A = 14 > 11 // true i.e., swap the both element positions.

Pass 1 is complete.

Pass 2: Gap = floor(Gap / 2)

Gap = floor(4 / 2)  // in pass 1,

Gap was 4.

Gap = 2

Gap 2 means, if we consider the first element at index 0 then next element will be at index 0+2 = 2, and similarly this process applied till the end of index.

Compare the elements.

A > A = 11 > 19 // false

A[]1 > A = 18 > 30 // false

A > A = 19 > 14 // true, i.e. swap the both element positions.

A > A = 11 > 14 // false

A > A = 30 > 40 //false

A > A = 19 > 29 // false

A > A = 40 > 37 // true, i.e. swap the both element positions.

A > A = 30 > 37 // false

A > A = 29 > 23 // true, i.e. swap the both element positions.

A > A = 19 > 23 // false

Pass 2 is complete.

Pass 3: Gap = floor(Gap/2)

Gap = floor(2 / 2)  // in pass 2, Gap was 2.

Gap = 1                 // i.e. last pass when gap is 1, shell sort is like the insertion sort. Compare the elements.

A > A = 11 > 18 // false

A > A = 18 > 14 // true i.e. swap the both element positions.

A > A = 11 > 14 // false

A > A = 18 > 30 // false A > A = 30 > 19 // true i.e. swap the both element positions. A > A = 18 > 19 // false

A > A = 30 > 37 // false A > A = 37 > 23 // true i.e. swap the both element positions. A > A = 30 > 23 // true i.e. swap the both element positions. A > A = 19 > 23 // false

A > A = 37 > 40 // false A > A = 40 > 29 // true i.e. swap the both element positions. A > A = 37 > 29 // true i.e. swap the both element positions. A > A = 30 > 29 // true i.e. swap the both element positions. A > A = 23 > 29 // false

Pass 3 is complete, and array is fully sorted.