Your One-Stop Solution to Understand Shell Sort Algorithm

Shell sort (also known as Shell sort or Shell's approach) is an in-place comparison-based sorting algorithm. In 1959, Donald Shell published the first version of the shell sort algorithm. Shell sort's execution time is strongly influenced by the gap sequence it employs. Shell sort is a sorting algorithm that is highly efficient and is based on the insertion sort algorithm. This algorithm avoids large shifts, as in insertion sort, where the smaller value is on the far right and must be moved to the far left. Shell Sort reduces its time complexity by utilising the fact that using Insertion Sort on a partially sorted array results in fewer moves.

What Is a Shell Sort Algorithm?


  • Shell sort is an in-place comparison sort that is also known as Shell sort or Shell's method.
  • It can be shown as a generalization of either exchange bubble sorting or insertion sorting.
  • The method begins by sorting pairs of elements far apart from each other, then gradually narrows the gap between elements to be compared. 
  • Some out-of-place elements can be moved into position faster than what a simple nearest-neighbor exchange would, by starting with far apart elements.

This algorithm uses insertion sort on widely spread elements to sort them and then sort the less widely spaced elements. This spacing is termed as the interval. 

This interval is calculated using Knuth's formula, which is as follows:

Knuth's Formula:

i = i * 3 + 1

Where i is the interval with a starting value of 1

You will now look at the operating procedure of the shell sort algorithm after understanding what it is.

Post Graduate Program: Full Stack Web Development

in Collaboration with Caltech CTMEEnroll Now
Post Graduate Program: Full Stack Web Development

How Does a Shell Sort Algorithm Work?

  • Consider the following example to have a better understanding of how shell sort works. You must use the same array as in the previous examples. For the purpose of clarity, you must use the interval of 4 as an example. 

Make a virtual sub-list of all values in the four-position interval. These are the values: (32, 17); (35, 21); (45, 27); and (13, 47).


  • You compare the values in each sub-list and swap them in the original array if necessary. After this step, the new array should look like this:


  • Then we pick one interval and divide it into two sub-lists: (17, 27, 32, 45) and (21, 13, 35, 47).


  • You compare the values in the original array and, if necessary, swap them. This is how the array should look after this step:


  • Finally, you need to use interval 1 to sort the rest of the array. The array is sorted by shell sort using insertion sort.

The following is a step-by-step guide:


You will now look at the shell sort algorithm's algorithm and pseudocode after seeing how it works.

Algorithm and Pseudocode of Shell Sort Algorithm

Algorithm for the Shell Sort Algorithm 

Step 1: Set the value of i.

Step 2: Separate the list into sub-lists with the same i interval.

Step 3: Using insertion sort, sort these sub-lists.

Step 4: Continue until the entire list has been sorted.

Pseudocode for the Shell Sort Algorithm

procedure begin shell sort()

   Array: array of items 

      while inter < Array.length /3 do: // calculating the interval (inter)

      inter = inter * 3 + 1     

   end while

   while inter > 0 do:

      for out = inter; out < Array.length; out++ do:

      value = Array[out] // select the inserted value

      in= out;

         while in > inter -1 && Array[in - inter] >= value do: //shifting value to right

            Array[in] = Array[in - inter]

            in = in - inter

         end while   

      Array[in] = value // insert the number at position

      end for

   inter = (inter -1) /3; // calculating interval

   end while

end procedure

You will look at the complexity of the shell sort algorithm in the next segment of this tutorial.

New Course: Full Stack Development for Beginners

Learn Git Command, Angular, NodeJS, Maven & MoreEnroll Now
New Course: Full Stack Development for Beginners

The Complexity of the Shell Sort Algorithm

The Time Complexity of the Shell Sort Algorithm

  • Complexity in the Worst-Case Scenario: Less Than or Equal to O (n2)

Shell sort's worst-case complexity is always less than or equal to O. (n2).

The worst-case complexity for shell sort, according to the Poonen Theorem, is (N log N)2/(log log N)2, or (N log N)2/log log N), or (N(log N)2), or something in between.

  • Complexity in the Best Case: O(n*Log n) 

The total number of comparisons for each interval (or increment) is equal to the size of the array when it is already sorted.

  • Complexity in the Average Case: O(n*log n) 

It's somewhere around O. (n1.25).

The degree of complexity is determined by the interval picked. The above complexity varies depending on the increment sequences used. The best increment sequence has yet to be discovered.

The Space Complexity of the Shell Sort Algorithm

  • The space complexity of the shell sort algorithm is O(1).

After learning about the complexity of the shell sort algorithm, you will look at some of its applications.

Applications of Shell Sort Algorithm 

Shell Sort can be used for a variety of purposes, including:

  • Shell sort has a more significant cache miss percentage than quicksort and executes more operations.
  • However, some versions of the qsort function in the C standard library geared at embedded devices utilize it instead of quicksort because it requires less code and does not use the call stack. The uClibc library, for example, uses Shell sort. The Linux kernel has a Shell Sort implementation for similar reasons.
  • Shell sort can also be used as a sub-algorithm of the introspective sort to sort short subarrays and avoid slowdowns when the recursion depth exceeds a certain threshold. This method is used in the bzip2 compression algorithm, for example.

In this tutorial, you will look at how to code the shell sort algorithm in C.

Full Stack Web Developer Course

To become an expert in MEAN StackView Course
Full Stack Web Developer Course

Code Implementation of Shell Sort Algorithm

The shell sort algorithm is implemented in the code below.

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

void shellsortalgorithm(int array[], int number)


    int i, j, k, temp;

    for (i = number / 2; i > 0; i = i / 2)


        for (j = i; j < number; j++)


            for(k = j - i; k >= 0; k = k - i)


                if (array[k+i] >= array[k])




                    temp = array[k];

                    array[k] = array[k+i];

                    array[k+i] = temp;






int main()


    int array[30];

    int k, values;

    printf("Enter total no. of elements : ");

    scanf("%d", &values);

    printf("\nEnter the %d values: ", values);

    for (k = 0 ; k < values; k++)


        scanf("%d", &array[k]);


    shellsortalgorithm(array, values);

    printf("\n Array after the sorting: ");

    for (k = 0; k < values; k++)

        printf("%d ", array[k]);

    return 0;




Advance your career as a MEAN stack developer with the Full Stack Web Developer - MEAN Stack Master's Program. Enroll now!

Next Steps

You learned everything there is to know about the shell sort algorithm in this tutorial, including how to implement and utilize it.

You will return to another fascinating topic in data structure and algorithms. Enroll in Simplilearn's Full Stack Web Development PGP to gain a better understanding of data structures and programming languages.

Please leave any comments or questions about the "shell Sort Algorithm" instruction in the space provided below. We will gladly help you resolve your queries as soon as possible.

Please stay safe until then and subscribe to the Simplilearn channel.

About the Author


Simplilearn is one of the world’s leading providers of online training for Digital Marketing, Cloud Computing, Project Management, Data Science, IT, Software Development, and many other emerging technologies.

View More
  • Disclaimer
  • PMP, PMI, PMBOK, CAPM, PgMP, PfMP, ACP, PBA, RMP, SP, and OPM3 are registered marks of the Project Management Institute, Inc.
  • *According to Simplilearn survey conducted and subject to terms & conditions with Ernst & Young LLP (EY) as Process Advisors