Author
Swaminathan Iyer
Product @ Interview Kickstart | Ex Media.net | Business Management - XLRI Jamshedpur. Loves building things and burning pizzas!
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:
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.
Following are some of the applications of the shell sort algorithm:
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:
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.
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
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.
#include
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;
}
Output:
Unsorted array: 12 17 4 9 3 6 13 1
Sorted Array: 1 3 4 6 9 12 13 17
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.
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:
When the array is already sorted, the total number of comparisons for each interval is equal to the size of the array:
The auxiliary space complexity of shell sort is O(1).
Question 1: What are the factors on which the time complexity of shell sort depends?
Answer:Â
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.
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.
———–
Article contributed by Abhinav Tiwari
Time Zone:
Get your enrollment process started by registering for a Pre-enrollment Webinar with one of our Founders.
The 11 Neural “Power Patterns” For Solving Any FAANG Interview Problem 12.5X Faster Than 99.8% OF Applicants
The 2 “Magic Questions” That Reveal Whether You’re Good Enough To Receive A Lucrative Big Tech Offer
The “Instant Income Multiplier” That 2-3X’s Your Current Tech Salary
The 11 Neural “Power Patterns” For Solving Any FAANG Interview Problem 12.5X Faster Than 99.8% OF Applicants
The 2 “Magic Questions” That Reveal Whether You’re Good Enough To Receive A Lucrative Big Tech Offer
The “Instant Income Multiplier” That 2-3X’s Your Current Tech Salary
Just drop your name and email so we can send your Power Patterns PDF straight to your inbox. No Spam!
By sharing your contact details, you agree to our privacy policy.
Time Zone: Asia/Dhaka
We’ve sent the Power Patterns PDF to your inbox — it should arrive in the next 30 seconds.
📩 Can’t find it? Check your promotions or spam folder — and mark us as safe so you don’t miss future insights.
We’re hosting a private session where FAANG insiders walk through how they actually use these Power Patterns to crack interviews — and what sets top performers apart.
🎯 If you liked the PDF, you’ll love what we’re sharing next.
Time Zone:
