# Shell Sort Program Code in C++

**Shell sort in c++ is the insertion sort but with some gap value**.

Basically, Gap value is the number of iteration to reach the next array element.

**In Insertion sort gap value =1**. That’s why we compare an array element with its adjacent element of 1 index far way and so on.

Shell sort is same like insertion sort. In fact **more efficient than insertion sort**.

It is because instead of comparing values 1 index away, We start comparing values with the index difference of gap=length/2 and decreasing the gap value, so on.

This makes array more sorted till we reach insertion sorting stage ie gap=1.

When finally the gap=1, then it becomes insertion sort.

## Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | #include <iostream> using namespace std; int main() { int newElement,gap; //Initializing array with default values int arr[] = {5, -35, 8, 56, 54, 11 ,-1}; //Calculating length of th array int sizeArr = sizeof(arr)/sizeof(arr[0]); for(int i=(sizeArr/2); i>=1; i=i/2){ gap = i; for(int j=i; j<sizeArr; j++){ newElement = arr[j]; //Insertion sort with gap=i while(arr[j-gap] > newElement && j>=gap ){ arr[j]=arr[j-gap]; j=j-gap; } arr[j] = newElement; } } for(int i=0;i<sizeArr;i++){ cout << arr[i]<< " "; } return 0; } |

## Online Compiler

### Output

1 | -35 -1 5 8 11 54 56 |

## Shell Sort

**In-place algorithm**(We work on the original array).- Difficult to compute time complexity because it will depend on gap value.
- Worst case:
**O(n²)**, Usually it performs much better than this. - U
**nstable algorithm**(same numbers can be interchanged which is useless)

Also Read: