04 Shell Sort

Shell sort is an improvement on Insertion Sort that:

  • - Starts by comparing elements far apart from each other,

  • - Then reduces the gap between elements step-by-step,

  • - Until finally it does a normal insertion sort with gap = 1.

This “GAP Strategy” helps move elements closer to their final position early on, so the final sort is way faster.

Shell sort starts out using a larger gap value, instead of comparing Neighbours, so as the algorithm runs it reduces the gap that it is using. It reduces the gap value until the gap value is one. When the gap value is one then basically, we are doing the Insertion Sort.

But at this point, the array will be more sorted than it was at the beginning. And so essentially what Shell sort does is it does some preliminary work using gap values that are greater than one and that preliminary work puts the elements in the array and perhaps closer to their sorted positions and then at the very last iteration when the gap value becomes one, it does an insertion sort. And because of the of that, there will be a lot less shifting required.

Question is, what do we use for the gap value? How to figure out what to start with and how to reduce it?

One common sequence that is used for the gap value is called the interval and it is called Knuth Sequence.

Here is a sample chart:

🎴 Real-Life Analogy: Sorting Books on a Long Shelf

Imagine you have 100 books randomly placed on a long shelf, and you want to sort them by title.

If you use Insertion Sort, you move one book at a time — which means a LOT of shifting.

But with Shell Sort, you do something smarter:

  1. 1. First, compare and sort books that are far apart — maybe every 10 books.

  2. 2. That moves a lot of books closer to where they belong.

  3. 3. Then you do it again, but with a smaller gap — say every 5 books.

  4. 4. Then again with gap 2, and finally gap 1 (regular insertion sort).

By the time you're doing the final pass, everything is almost sorted, so it finishes super fast.

🔁 How It Works (Example)

Let's say we have this array:

csharp

CopyEdit

[9, 8, 3, 7, 5, 6, 4, 1]

Step-by-step:

1⃣ Start with a big gap (say gap = 4):

Compare and sort:

  • 9 and 5

  • 8 and 6

  • 3 and 4

  • 7 and 1

After sorting each pair:

csharp

CopyEdit

[5, 6, 3, 1, 9, 8, 4, 7]

2⃣ Reduce the gap (gap = 2):

Now compare and sort:

  • 5 and 3

  • 6 and 1

  • 3 and 9

  • etc.

The list gets more and more sorted...

3⃣ Final gap = 1 (normal insertion sort):

At this point, most elements are already close to their final spots, so sorting is really fast.

📊 Performance

Feature

Shell Sort

✅ In-place memory?

Yes (no extra memory used)

⏱ Time Complexity

Depends on the gap, but much faster than bubble/insertion/selection (best around O(n log n))

🚀 Best Use Case

Medium or large datasets where simplicity and speed are both needed

📌 Stable?

❌ Not stable (may change the order of equal elements)

📦Summary:

  • - Shell Sort = insertion sort with turbo boost.

  • - It starts by sorting elements far apart.

  • - Each round, it shrinks the gap and sorts again.

  • - It’s way faster than bubble, selection, or insertion sort, especially for big lists.