# Shell Sort

- Shell Sort Algorithm
- Shell Sort Example
- Shell Sort Algorithm Implementation
- Shell Sort Algorithm Complexity

If you don’t know what insertion sort is then, please go through the insertion sort article first.

Shell sort is a highly efficient comparison-based sorting algorithm. It is seen as the generalization of the bubble sort algorithm or an optimized insertion sort algorithm. In the insertion sort algorithm, we move elements one position ahead. But in the case of shell sort, we move elements `h`

positions ahead. It starts by sorting very far elements and gradually reduces the gap based on a sequence to sort the whole array. Some of the sequences used are:

Shell’s original sequence | `N/2, N/4,..., 1` |

Papernov & Stasevich | `1, 3, 5, 9,...` |

Hibbard | `1, 3, 7, 15, 31, 63,...` |

Knuth | `1, 4, 13, ... , (3k – 1) / 2` |

Pratt | `1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, ....` |

Sedgewick | `1, 8, 23, 77, 281, ... 4j+1+ 3·2j+ 1` |

## Shell Sort Algorithm

Let us assume that we have an unsorted array `A[]`

containing `n`

elements. We will use the shell’s original sequence to sort the array.

##### Calculate the value of the

`gap`

as per the sequence.##### For every subarray at an interval equal to the

`gap`

do the following:##### Sort using insertion sort.

##### Repeat the above process until the complete array is sorted.

## Shell Sort Example

Suppose we have the array: `(9, 8, 3, 7, 5, 6, 4, 1)`

. We will sort it using the shell sort algorithm and use the shell’s original sequence to reduce the gap intervals.

- First Iteration

`n/2`

= 4 , elements lying at interval `4`

are compared and swapped.

`A[0]`

> `A[4]`

→ swapped, `(5,8,3,7,9,6,4,1)`

.

`A[1]`

> `A[5]`

→ swapped, `(5,6,3,7,9,8,4,1)`

.

`A[2]`

< `A[6]`

`A[3]`

> `A[7]`

→ swapped, `(5,6,3,1,9,8,4,7)`

.

The array becomes: `(5,6,3,1,9,8,4,7)`

.

- Second Iteration

`n/4`

= 2 , element lying at interval `2`

are compared and swapped.

`A[0]`

> `A[2]`

→ swapped, `(3,6,5,1,9,8,4,7)`

.

`A[1]`

> `A[3]`

→ swapped, `(3,1,5,6,9,8,4,7)`

.

`A[0]`

< `A[2]`

< `A[4]`

`A[1]`

< `A[3]`

< `A[5]`

`A[2]`

> `A[4]`

and `A[4]`

> `A[6]`

→ swapped, `(3,1,4,6,5,8,9,7)`

.

`A[1]`

< `A[3]`

< `A[5]`

but `A[5]`

> `A[7]`

→ swapped, `(3,1,4,6,5,7,9,8)`

.

The array becomes: `(3,1,4,6,5,7,9,8)`

.

- Third Iteration

`n/8`

= 1 , element lying at interval `1`

are compared and swapped.

`A[0] > A[1]`

→ swapped, `(1,3,4,6,5,7,9,8)`

.

`A[0] .. A[2]`

→ sorted

`A[0] .. A[3]`

→ sorted

`A[0] .. A[3]`

→ sorted but A[3] > A[4] → swapped, `(1,3,4,5,6,7,9,8)`

.

`A[0] .. A[5]`

→ sorted

`A[0] .. A[6]`

→ sorted

`A[0] .. A[6]`

→ sorted but A[6] > A[7] → swapped, `(1, 3, 4, 5, 6, 7, 8, 9)`

.

## Shell Sort Algorithm Implementation

```
#include<bits/stdc++.h>
using namespace std;
void shellSort(int arr[], int n)
{
for (int gap = n / 2; gap > 0; gap /= 2)
{
for (int i = gap; i < n; i += 1)
{
int temp = arr[i];
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
arr[j] = arr[j - gap];
arr[j] = temp;
}
}
}
int main() {
int n = 8;
int arr[8] = {9, 8 ,3 ,7, 5, 6, 4, 1};
cout << "Input arr: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
shellSort(arr, n); // Sort elements in ascending order
cout << "Output arr: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
}
```

## Shell Sort Algorithm Complexity

### Time Complexity

- Average Case

The complexity depends on the sequence chosen for sorting. The time complexity is of the order of [Big Theta]: O(nlog(n)^{2}).

- Worst Case

The worst-case time complexity for shell sort is always less than equal to O(n^{2}). More precisely according to Poonen’s theorem, it is given by Θ(nlogn)^{2}/(log log n)^{2}) or Θ(nlog n)^{2}/log log n) or Θ(n(log n)^{2}) or something in between. The worst-case time complexity is [Big O]: less than equal to O(n^{2}).

- Best Case

The best-case occurs when the array is already sorted and the comparisons required for each interval is the same as the size of the array. The best-case time complexity is [Big Omega]: `O(nlogn)`

.

### Space Complexity

Space Complexity for the Shell sort algorithm is `O(n)`

because no extra memory other than a temporary variable is required.