# Shell Sort

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(n2) 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);
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)`

### Applications of Shell Sort

Shell Sort is used when:

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

#### Sorting Algorithms

Here, We will learn about sorting algorithms, why is sorting necessary, classification and complexity of…

#### Insertion Sort

Here, We will learn about insertion sort in C, their algorithm, implementation code in C,…

#### Group Anagrams LeetCode Solution

Given an array of strings strs, group the anagrams together. You can return the answer…

#### Merge Sort

Here, We will discuss about Merge Sort in C, their algorithm, implementation code in C,…