Shell Sort

Explanation

- **Shell Sort** is an in-place comparison-based sorting algorithm that generalizes **Insertion Sort** to allow the exchange of far apart elements. It works by comparing elements that are a certain gap apart, and gradually reducing the gap.

-

• Steps:

  • Start with a large gap and reduce the gap until it becomes 1.
  • For each gap, perform Insertion Sort on the elements that are gap positions apart.

• Time Complexity:

  • Best Case: O(n log n)
  • Worst Case: O(n^2) (depending on gap sequence used).