# Shell Sort Algorithm- Explanation, Implementation and Complexity

Shell Sort is a generalized version of insertion sort. It is an in-place comparison sort. Shell Sort is also known as diminishing increment sort, it is one of the oldest sorting algorithms invented by Donald L. Shell (1959.)

This algorithm uses insertion sort on the large interval of elements to sort. Then the interval of sorting keeps on decreasing in a sequence until the interval reaches 1. These intervals are known as gap sequence.

This algorithm works quite efficiently for the small and medium-size arrays as its average time complexity is near O(n).

## 1. Key Points of Shell Sort Algorithm

• Shell sort is a comparison-based sorting.
• The time complexity of Shell Sort depends on the gap sequence. Its best-case time complexity is O(n* logn) and the worst case is O(n* log2n). The time complexity of Shell sort is generally assumed to be near to O(n) and less than O(n2) as determining its time complexity is still an open problem.
• The best case in shell sort is when the array is already sorted. The number of comparisons is less.
• It is an in-place sorting algorithm as it requires no additional scratch space.
• Shell Sort is an unstable sort as the relative order of elements with equal values may change.
• It is been observed that shell sort is 5 times faster than bubble sort and twice faster than insertion sort its closest competitor.
• There are various increment sequences or gap sequences in shell sort which produce various complexity between O(n) and O(n2).

### 1.1. Increment Sequences

1. Shell’s original sequence: N/2 , N/4 , …, 1 (repeatedly divide by 2);
2. Hibbard’s increments: 1, 3, 7, …, 2k – 1 ;
3. Knuth’s increments: 1, 4, 13, …, (3k – 1) / 2 ;
4. Sedgewick’s increments: 1, 5, 19, 41, 109, ….

## 2. Shell Sort Example of Even Size Array

Observe each step in the video below carefully and try to visualize the concept of this algorithm.

In this video, we observe that the gap sequence is taken as |N/2|, |N/4|……1.

Here is 3 Simple Steps explaining the shell sort alogrithm:

1. Initial interval is k (k=n/2=6), So we create virtual sublist of all values in interval of 6 i.e {61, 24}, {109, 119}, {149, 122}, {111, 125}, {34, 27}, {2, 145}. We apply insertion sort in all sublist and sort them.
We get sorted list as {24, 109, 122, 111, 27, 2, 61, 119, 149, 125, 34, 145}.
2. Then we decrease the interval ( k/2=6/2=3), we again create sublist in interval of 3 – {24, 111, 61, 125}, {109, 27, 119, 34}, {122, 2, 149, 145}. After applying insertion sort to these sublists we get our list as {24, 27, 2, 61, 34, 122, 111, 109, 145, 125, 119, 149}
3. We continue this process until interval decrease to 1.
Next (k/2=|3/2|=1), we just get a single list as the interval size is one. On applying insertion sort on it, we get our required sorted list- {2, 24, 27, 34, 61, 109, 111, 122, 125, 145, 149}.

## 3. Pseudocode of Shell Sort

```SHELL-SORT(A,n)
// we take gap sequence in order of |N/2|, |N/4|, |N/8|...1
for gap=n/2; gap=0; gap/=2 do:
//Perform gapped insertion sort for this gap size.

for i=gap; i<n; i+=1 do: temp=A[i]
// shift earlier gap-sorted elements up until
// the correct location for a[i] is found
for j=i; j>=gap && A[j-gap]>temp;j-=gap
do: A[j]= A[j-gap]
end for
// put temp in its correct location
A[j]= temp;
end for
end for
end func```

In the above implementation of shell sort time complexity in the worst case is O(n2) as gap reduces by half in every iteration. To get better time complexity we can choose some other gap sequence as discussed above.

## 4. Asymptotic Analysis of Shell Sort

Since in this algorithm insertion sort is applied in the large interval of elements and then interval reduces in a sequence, therefore the running time of Shell sort is heavily dependent on the gap sequence it uses.

Summarising all this –
Worst Case Time complexity: O (n2)
Average Case Time complexity: depends on gap sequence.
Best Case Time complexity: O(n*logn)
Worst Case Space Complexity: O(n) total, O(1) auxiliary
Data Structure: Array
Sorting In Place: Yes
Stable: No

## 5. Implementation of Shell Sort in various programming language

### 5.1. Shell Sort implementation in C Language

```#include <math.h>
#include <stdio.h>
#include <stdlib.h>

/* function to sort array using shellSort */
void shellSort(int A[], int n) {
int gap, i;
// Start with a larger gap, then reduce the gap to 1
// we take gap sequence in order of |N/2|, |N/4|, |N/8|...1
for (gap = n / 2; gap > 0; gap /= 2) {
// we performe gapped insertion sort for this gap size.
// The first gap elements a[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 += 1) {
// store a[i] in temp and make a hole at position i
int temp = A[i];
// shift earlier gap-sorted elements up until the correct
// location for a[i] is found
int j;
for (j = i; j >= gap & amp; &amp; A[j - gap] > temp; j -= gap)
A[j] = A[j - gap];

// put temp (the original a[i]) in its correct location
A[j] = temp;
}
}
}

/* function to print an array */
void print_array(int A[], int size) {
int i;
for (i = 0; i < size; i++)
printf("%d ", A[i]);
printf("\n");
}

int main() {

int A[] = {61, 109, 149, 111, 34, 2, 24, 119, 122, 125, 27, 145};
int n = sizeof(A) / sizeof(A);

printf("Unsorted array: ");
print_array(A, n);
printf("\n");
// Call shell sort function
shellSort(A, n);

printf("Sorted array: ");
print_array(A, n);
return 0;
}
```

### 5.2. Shell Sort implementation in Java

```package com.codingeek;

import java.util.Arrays;

public class ShellSort {
/* An utility function to print array of size n */

/* function to sort array using shellSort */
void sort(int A[]) {
int n = A.length;

// Start with a larger gap, then reduce the gap to 1
// we take gap sequence in order of |N/2|, |N/4|, |N/8|...1
for (int gap = n / 2; gap > 0; gap /= 2) {
// we perform gapped insertion sort for this gap size.
// The first gap elements a[0..gap-1] are already
// in gapped order keep adding one more element
// until the entire array is gap sorted
for (int i = gap; i < n; i += 1) {
// store a[i] in temp and make a hole at
// position i
int temp = A[i];
// shift earlier gap-sorted elements up until
// the correct location for a[i] is found
int j;
for (j = i; j >= gap && A[j - gap] > temp; j -= gap)
A[j] = A[j - gap];

// put temp (the original a[i]) in its correct
// location
A[j] = temp;
}
}
}

// Driver method
public static void main(String args[]) {
int arr[] = { 61, 109, 149, 111, 34, 2, 24, 119, 122, 125, 27, 145 };
// print unsorted array using Arrays.toString()
System.out.print("Unsorted array: ");
System.out.println(Arrays.toString(arr));

ShellSort ob = new ShellSort();
ob.sort(arr);

System.out.print("Sorted array: ");
// print sorted array
System.out.println(Arrays.toString(arr));
}
}```
```Output:-
Unsorted array:  61,109,149,111,34,2,24,119,122,125,27,145
Sorted array:    2,24,27,34,61,109,111,122,125,145,149
```

Shell Sort is one of the fastest comparison sort. It is easy to understand and easy to implement but its time complexity analysis is sophisticated. Its time complexity is still debatable topic but it lies between O(n) and O(n2). A good programmer must be aware of this sorting algorithm.

Shellsort is now rarely used in serious applications. It performs more operations and has higher cache miss ratio than quicksort.(wiki)

Data Structure tutorials
Algorithm Tutorials

All examples are hosted on Github.

An investment in knowledge always pays the best interest. I hope you like the tutorial. Do come back for more because learning paves way for a better understanding

Do not forget to share and Subscribe.

Happy coding!! ?

### Recommended -

Subscribe
Notify of Inline Feedbacks mandy
2 years ago

you should change the title of
first code from merge sort to shell sort. dunce
1 year ago

Clear as mud. Could follow up to k=6 but completely lost after k=3. How does the algorithm know how to backtrack. Is the shell sort recursive?

1 year ago

Hi @dunce, Shell sort neither backtrack nor it is recursive.
It simply starts selecting the window to compare two values and sort the array partially so that it is sorted more with each iteration..
It reduces the number of comparisons and then the array is finally sorted in the last iteration.

3
0