In this article, we will be discussing about Shell Sort algorithm in C, C++, Java etc. Shell sort algorithm working, implementation, pseudo-code, time complexity, etc are also discussed here.

**What is Shell Sort Algorithm?**

Shell sort algorithm is **very similar to that of the Insertion sort algorithm**. In case of Insertion sort, we move elements one position ahead to insert an element at its correct position. Whereas here, Shell sort starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared. Starting with far apart elements, it can move some out-of-place elements into the position faster than a simple nearest-neighbor exchange.

**A simple look at Shell Sort Vs Insertion Sort**

**Shelling out the Shell Sort Algorithm with Examples**

Here is an example to help you understand the working of Shell sort on array of elements name A = {17, 3, 9, 1, 8}

**Shell Sort in C, C++, Java**

Here is the implementation of Shell sort in C, C++ and Java.

#include<stdio.h>

int main()

{

int n, i, j, temp, gap;

scanf("%d", &n);

int arr[n];

for(i = 0; i < n; i++)

{

scanf("%d", &arr[i]);

}

for (gap = n/2; gap > 0; gap = gap / 2)

{

// Do a gapped insertion sort

// The first gap elements arr[0..gap-1] are already in gapped order

// keep adding one more element until the entire array is gap sorted

for (i = gap; i < n; i = i + 1)

{

// add arr[i] to the elements that have been gap sorted

// save arr[i] in temp and make a empty space at index i

int temp = arr[i];

// shift earlier gap-sorted elements up until the correct location for arr[i] is found

for (j = i; j >= gap && arr[j - gap] > temp; j = j - gap)

arr[j] = arr[j - gap];

// put temp (the original arr[i]) in its correct position

arr[j] = temp;

}

}

for(i = 0; i < n; i++)

{

printf("%d ", arr[i]);

}

}

#include<iostream>

using namespace std;

int main()

{

int n, i, j, temp, gap;

cin >> n;

int arr[n];

for(i = 0; i < n; i++)

{

cin >> arr[i];

}

for (gap = n/2; gap > 0; gap = gap / 2)

{

// Do a gapped insertion sort

// The first gap elements arr[0..gap-1] are already in gapped order

// keep adding one more element until the entire array is gap sorted

for (i = gap; i < n; i = i + 1)

{

// add arr[i] to the elements that have been gap sorted

// save arr[i] in temp and make a empty space at index i

int temp = arr[i];

// shift earlier gap-sorted elements up until the correct location for arr[i] is found

for (j = i; j >= gap && arr[j - gap] > temp; j = j - gap)

arr[j] = arr[j - gap];

// put temp (the original arr[i]) in its correct position

arr[j] = temp;

}

}

for(i = 0; i < n; i++)

{

cout << arr[i] << " ";

}

}

import java.util.Scanner;

public class Main

{

public static void main(String args[])

{

Scanner sc = new Scanner(System.in);

int i, j, temp, gap;

int n = sc.nextInt();

int arr[] = new int[n];

for(i = 0; i < n; i++)

{

arr[i] = sc.nextInt();

}

for (gap = n/2; gap > 0; gap = gap / 2)

{

// Do a gapped insertion sort

// The first gap elements arr[0..gap-1] are already in gapped order

// keep adding one more element until the entire array is gap sorted

for (i = gap; i < n; i = i + 1)

{

// add arr[i] to the elements that have been gap sorted

// save arr[i] in temp and make a empty space at index i

temp = arr[i];

// shift earlier gap-sorted elements up until the correct location for arr[i] is found

for (j = i; j >= gap && arr[j - gap] > temp; j = j - gap)

arr[j] = arr[j - gap];

// put temp (the original arr[i]) in its correct position

arr[j] = temp;

}

}

for(i = 0; i < n; i++)

{

System.out.print(arr[i] + " ");

}

}

}

**Shell Sort Time Complexity**

Time complexity of above implementation of shellsort is O(n^{2}). In the above implementation, gap is reduced by half in every iteration.