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 small and medium size array as its average time complexity is near to O(n).


Here are some key points of shell sort algorithm –

  • Shell Sort is a comparison based sorting.
  • Time complexity of Shell Sort depends on gap sequence . Its best case time complexity is O(n* logn) and worst case is O(n* log2n). 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 unstable sort as 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).

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, ….

Let’s understand it with an 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 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 util interval decrease to 1.
    Next (k/2=|3/2|=1), so we just get a single list as 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}.

Pseudocode of Merge 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.


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


Implementation of Shell Sort in various programming language

C


/* C implementation ShellSort */
#include<stdio.h>
#include<stdlib.h>
#include<math.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 && 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;
}

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)

Knowledge is most useful when liberated and shared. Share this to motivate us to keep writing such online tutorials for free and do comment if anything is missing or wrong or you need any kind of help.

Keep Learning… Happy Learning.. :)