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(n²).

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, …, 2^k – 1 ;
3. Knuth’s increments: 1, 4, 13, …, (3^k – 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(n²) 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 (n²)
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[0]);

  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(n²). 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)

Helpful Links

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 -