Shell sort in C, C++, Java is the insertion sort but with some gap value.

Basically, Gap value is the number of iteration to reach the next array element.

In Insertion sort gap value =1. That’s why we compare an array element with its adjacent element of 1 index far way and so on.

Shell sort is same like insertion sort. In fact more efficient than insertion sort.

It is because instead of comparing values 1 index away, We start comparing values with the index difference of gap=length/2 and decreasing the gap value & so on.

This makes array more sorted till we reach insertion sorting stage ie gap=1.

When finally the gap=1, then it becomes insertion sort.

Shell Sort Code





Shell Sort Overview

  • In-place algorithm(We work on the original array).
  • Difficult to compute time complexity because it will depend on gap value.
  • Worst case: O(n²), Usually it performs much better than this.
  • Unstable algorithm (same numbers can be interchanged which is useless)

Leave a Reply