Register for our webinar

How to Nail your next Technical Interview

1 hour
Enter details
Select webinar slot
*Invalid Name
*Invalid Name
By sharing your contact details, you agree to our privacy policy.
Step 1
Step 2
You have registered for our webinar
Oops! Something went wrong while submitting the form.
Enter details
Select webinar slot
*All webinar slots are in the Asia/Kolkata timezone
Step 1
Step 2
You are scheduled with Interview Kickstart.
Oops! Something went wrong while submitting the form.
Iks white logo

You may be missing out on a 66.5% salary hike*

Nick Camilleri

Head of Career Skills Development & Coaching
*Based on past data of successful IK students
Iks white logo
Help us know you better!

How many years of coding experience do you have?

Thank you! Your submission has been received!
Oops! Something went wrong while submitting the form.
Iks white logo

FREE course on 'Sorting Algorithms' by Omkar Deshpande (Stanford PhD, Head of Curriculum, IK)

Thank you! Please check your inbox for the course details.
Oops! Something went wrong while submitting the form.
Our June 2021 cohorts are filling up quickly. Join our free webinar to Uplevel your career
closeAbout usWhy usInstructorsReviewsCostFAQContactBlogRegister for Webinar

Attend our Free Webinar on How to Nail Your Next Technical Interview


How To Nail Your Next Tech Interview

Learn Shell Sort Algorithm
Hosted By
Ryan Valles
Founder, Interview Kickstart
Our tried & tested strategy for cracking interviews
prepare list
How FAANG hiring process works
hiring process
The 4 areas you must prepare for
hiring managers
How you can accelerate your learnings
The fast well prepared banner

Learn Shell Sort Algorithm

The topic of sorting algorithms is a crucial one for software engineers, especially if you are preparing for a coding interview. During tech interviews, you will face many challenging problems that will put your data structure and algorithms knowledge to test. Sorting algorithms are the key to solving many such problems. 

In this article, we’ll go over the shell sort algorithm. We’ll cover:

  • What Is Shell Sort?
  • How Does Shell Sort Work?
  • Shell Sort Algorithm
  • Shell Sort Pseudocode
  • Shell Sort Code
  • Shell Sort Complexities
  • Advantages of Shell Sort
  • Disadvantages of Shell Sort
  • FAQs on Shell Sort 

What Is Shell Sort?

Shell sort algorithm is a generalization of insertion sort, which uses the fact that insertion sort works efficiently on an input that is already almost sorted. It improves insertion sort by comparing and exchanging elements that are far apart. 

In short, shell sort works by sorting elements at a specific interval using insertion sort. The interval between the elements is gradually decreased based on the increment sequence used. Shell sort’s performance also depends on the type of sequence used. (We’ll talk about these sequences shortly!) 

The last step of shell sort is the same as insertion sort, but the elements are already almost sorted by then. 

Real-World Applications of Shell Sort

Following are some of the applications of the shell sort algorithm:

  • Shell sort is used in the Linux kernel because it does not use a call stack.
  • uClibc library uses Shell sort.
  • Shell sort is used in the bzip2 compressor to avoid problems that could come when sorting algorithms exceed a language’s recursion depth.

How Does Shell Sort Work? 

Let’s assume that the array Arr[] = {12, 17, 4, 9, 3, 6, 13, 1} is to be sorted.

We’ll use the sequence (N/2, N/4, ...1) as intervals in our algorithm.

Here, “interval” refers to the distance of index between two elements of an array that will be placed in the same sublist. By N/2, we mean floor(N/2).
In our outer loop, we will iterate over the elements of the sequence we have chosen in decreasing order (here, our sequence is N/2, N/4, … 1)
In the first iteration, the interval is N/2 = 4. So, in our inner loop, we sort all the sublists of every 4th element. 

In the figure above:

Sublist 1: {12, 3}
Sublist 2: {17, 6}
Sublist 3: {4, 13}
Sublist 4: {9, 1}

After sorting all sublists, we get:

Now, in the second iteration, the interval is N/4 = 2 — we sort all sublists of every 2nd element:

Sublist 1: {3,4,12,13}
Sublist 2: {6,1,17,9}

After sorting all sublists, we have:

Finally, in the third iteration, the interval is N/8 = 1. So, we perform insertion sort. 

Sublist 1: {3, 1, 4, 6, 12, 9, 13, 17}

The result after sorting:

There are many increment sequences that can be used for shell sort, and as mentioned before, the time complexity of the process can vary based on the sequence chosen. Following are some of the increment sequences used in shell sort:

  • Sedgewick’s increment sequence: 1, 8, 23, 77, 281 … 4^(n+1) + 3*2^n +1
    Time complexity: O(N^(4/3))
  • Papernov and Stasevich increment sequence: 1, 3, 5, 9, 17 … 2^k +1
    Time complexity: O(N^(3/2))
  • Pratt’s increment sequence: 1, 2, 3, 4, 6, 8, 9, 12 … ((2^n)*(3^m))
    Time complexity: O(N*logN*logN)

Shell Sort Algorithm

The shell sort algorithm consists of three steps:

Step 1: Initialize h (interval) with N/2 and divide it by 2 in every iteration until it becomes 1.
Step 2: Divide the array into smaller sub-lists of equal interval h.
Step 3:
Sort all sub-lists using insertion sort. Repeat Steps 2 and 3 until the array is sorted.

Shell Sort Pseudocode 

Here's the pseudocode for shell sort. You can use as a reference this to code in any programming language you prefer.

h: interval

N: Size of array

for h from N/2 to 1, do

    Put all the elements which are at the distance of h in a sublist   

    And sort all sublists using insertion sort.

return Arr

Shell Sort Code

We’ve used C++ to demonstrate how shell sort works. Use this as a reference to code in C, Java, Python, or any programming language of your choice.

using namespace std;
void Shellsort(int Arr[], int N)
    // Changing interval as (N/2, N/4 ... 1) sequence
    for(int h = N / 2; h >= 1; h /= 2)
        //sorting each sub-list using insertion sort
        for(int i = h; i < N; i++)
            int temp = Arr[i];
            int j;

            for(j = i; j >= h && Arr[j - h] > temp; j -= h)
                Arr[j] = Arr[j - h];

            Arr[j] = temp;
        h /= 2;

int main()
    const int N = 8;
    int Arr[N] = {12, 17, 4, 9, 3, 6, 13, 1};
    cout << "Unsorted array: ";
    for (int i = 0; i < N ; i++)
        cout << Arr[i] << " ";
    cout << endl;
    Shellsort(Arr, N);
    cout << "Sorted Array: ";
    for (int i = 0; i < N; i++)
        cout << Arr[i] << " ";
    cout << endl;
    return 0;


Unsorted array: 12 17 4 9 3 6 13 1

Sorted Array: 1 3 4 6 9 12 13 17

Shell Sort Complexities

While the performance of shell sort depends on the sequence selected, let’s look at how our implementation does in terms of time and space complexity. 

Time Complexity

The worst- and average-case time complexity of shell sort depends on the interval sequence  — we choose the (N/2, N/4, ... 1) sequence.
The time complexity of our implementation is O(N*N). This can be improved by choosing different sequences for reducing h (interval).

Let’s break down how we got O(N*N):

Consider an array where all the even-positioned elements are greater than the median. The odd and even elements are not compared until we reach the last increment of 1. The number of compare/exchanges needed for the last iteration is O(N*N). Therefore:

  • Worst-case time complexity: O(N*N)
  • Average-case time complexity: O(N*logN)

When the array is already sorted, the total number of comparisons for each interval is equal to the size of the array:

  • Best-case time complexity: O(N*logN)

Space Complexity

The auxiliary space complexity of shell sort is O(1).

Advantages of Shell Sort 

  • Implementation is easy.
  • No stack call is required.
  • Shell sort is efficient when given data is already almost sorted.
  • Shell sort is an in-place sorting algorithm.

Disadvantages of Shell Sort

  • Shell sort is inefficient when the data is highly unsorted.
  • Shell sort is not efficient for large arrays.

Shell Sort vs. Quicksort

  • On average, quicksort performs better than shell sort; but shell sort is more efficient than quicksort when the given data is already/almost sorted.
  • Shell sort does not require stack calls, whereas quicksort does.

FAQs on Shell Sort

Question 1: What are the factors on which the time complexity of shell sort depends?


  • Shell sort is an adaptive algorithm. Its time complexity depends on how sorted the given data is.
  • Shell sort’s performance also depends on the interval sequence we choose, such as Knuth’s increment sequence or Sedgewick's increment sequence.

Question 2: Is shell sort stable?

Answer: Although insertion sort is stable, shell sort is not. Moving the elements using intervals makes the shell sort unstable.

For example, consider an array Arr[] = {4, 2, 2, 5}
Consider 0-based indexing.

Here, N/2 = 2.

So, we sort sublist {4, 2} and {2, 5}.

While sorting the first sublist {4, 2}, 4 and 2 will be swapped, and 2 (which was at index 2 initially) will move to index 0, and 2 (which was index 1 initially) will remain at its position. Therefore, shell sort is not stable.

Are You Ready to Nail Your Next Coding Interview?

Sorting algorithms interview questions feature in almost every coding interview for software developers. If you’re looking for guidance and help to nail these questions and more, sign up for our free webinar. 

As pioneers in the field of technical interview prep, we have trained thousands of software engineers to crack the toughest coding interviews and land their dream jobs at Google, Facebook, Apple, Netflix, Amazon, and other Tier-1 tech companies.

Sign up now!


Article contributed by Abhinav Tiwari

Last updated on: 
October 27, 2023

Swaminathan Iyer

Product @ Interview Kickstart | Ex | Business Management - XLRI Jamshedpur. Loves building things and burning pizzas!

Attend our Free Webinar on How to Nail Your Next Technical Interview


Learn Shell Sort Algorithm

Worried About Failing Tech Interviews?

Attend our webinar on
"How to nail your next tech interview" and learn

Hosted By
Ryan Valles
Founder, Interview Kickstart
blue tick
Our tried & tested strategy for cracking interviews
blue tick
How FAANG hiring process works
blue tick
The 4 areas you must prepare for
blue tick
How you can accelerate your learnings
Register for Webinar