This algorithm avoids large shifts as in case of insertion sort, if the smaller value is to the far right and has to be moved to the far left.

shell sort is a "diminishing Incremental Sort". better known as a "**comb Sort**"

This algorithm uses insertion sort on a widely spread elements, first to sort them and then sorts the less widely spaced elements.

Or it an be said this algorithm takes multiple passes through the list and each time sorts a number of equally sized sets using the insertion sort.

The size of the set to be sorted get larger with each pass through the the list, until the set consist of entire list .

The item contained in each set are not contiguous rather. If there are *i* sets that a set is composed of every *ith* element.

using namespace std;
// Shell sort
void shellSort(int a[], int n) {
// Rearrange elements at each n/2, n/4, n/8, ... intervals
for (int i = n / 2; i > 0; i /= 2) {
for (int j = i; j < n; j += 1) {
int temp = a[j];
int k;
for (k = j; k >= i && a[k - i] > temp; k -= i) {
a[k] = a[k - i];
}
a[k] = temp;
}
}
}
// Driver code
int main() {
int n,i;
cout<<"Enter No. of elements\n";
cin>>n;
int a[n];
cout<<"Enter elements of array\n";
for(i=0 ; i<n ; i++)
{
cin>>a[i];
}
int size = sizeof(a) / sizeof(a[0]);
shellSort(a, size);
cout << "Sorted array: \n";
for (i = 0; i < size; i++){
cout << a[i] << " ";
}
cout << endl;
return 0;
}

Output

Enter no. of elements

5

Enter elements of array

54

87

12

45

76

Sorted Array:

12 45 54 76 87

## Comments