Here, We will discuss about Shell Sort in C, their algorithm, implementation code in C, time and space complexity, and their applications.

**What is Shell Sort?**

**Shell Sort** also called diminishing increment sort. This sorting algorithm is a *generalization of **insertion sort.*

Shell sort is efficient for medium size lists. For bigger lists, the algorithm is not the best choice. It is the fastest of all O(n^{2}) sorting algorithms.

Shell sort is also known as n-gap insertion sort.

The algorithm based on the idea that sort the elements far apart from each other and successively reduces the interval between the elements to be sorted.

**Shell Sort Implementation**

#### Program code in C

```
//Shell sort in C programming
#include<stdio.h>
//shell sort
void shellsort(int arr[], int n)
{
for(int interval=n/2; interval>0; interval/=2)
{
for(int i=interval; i<n; i+=1)
{
int temp = arr[i];
int j;
for(j=i; j>=interval && arr[j-interval] > temp; j-=interval)
{
arr[j] = arr[j-interval];
}
arr[j] = temp;
}
}
}
//print an array
void printarray(int arr[], int n)
{
for(int i=0; i<n; i++)
{
printf("%d ",arr[i]);
}
printf("\n");
}
//Driver Code
int main()
{
int data[] = {8, 4, 35, 12, 1};
int size = sizeof(data) / sizeof(data[0]);
shellsort(data, size);
printf("Sorted array: ");
printarray(data, size);
}
```

Code language: C++ (cpp)

#### Output:

`Sorted array : 1 4 8 12 35`

Code language: PHP (php)

**Time and Space Complexity of Shell Sort**

Time Complexity | |

Worst Case | O(n log^{2}n) |

Best Case | O(n) |

Average Case | depend on gap sequence |

Space Complexity | |

Worst Case | O(n) |

**Applications of Shell Sort **

Shell Sort is used when:

- calling a stack is overhead. uClibc library uses this sort.
- recursion exceeds a limit. bzip2 compressor uses it.

### Related:

*Want to Contribute*:-

If you like “**To The Innovation**” and want to contribute, you can mail your articles to **[email protected]**. See your articles on the main page and help other coders.