Shell Sort

Medium

Shell Sort

Shell sort is an improved insertion sort that compares and swaps elements far apart, halving the gap each round. By arranging the big picture with large gaps first, the final gap=1 insertion sort is nearly done, making it efficient.

📊 Complexity

Type	Value
Best	O(n log n)
Average	O(n^1.5)
Worst	O(n²)
Space	O(1)

🏷️ Tags

SortingImproved Insertion SortComparison SortGap Sequence

📖 Introduction

Shell sort performs insertion sort on elements spaced a certain gap apart, gradually shrinking the gap and finishing with gap=1 (plain insertion sort). It was devised by Donald Shell.

1/32

🚀Start Shell Sort

Let's sort the array. Shell sort first insertion-sorts elements that are a gap apart, then halves the gap to sort more finely. The gap shrinks 4 → 2 → 1.

🔒

Shell Sort

Medium

Shell Sort

📊 Complexity

Type	Value
Best	O(n log n)
Average	O(n^1.5)
Worst	O(n²)
Space	O(1)

🏷️ Tags

SortingImproved Insertion SortComparison SortGap Sequence

📖 Introduction

Shell sort performs insertion sort on elements spaced a certain gap apart, gradually shrinking the gap and finishing with gap=1 (plain insertion sort). It was devised by Donald Shell.

1/32

🚀Start Shell Sort

Let's sort the array. Shell sort first insertion-sorts elements that are a gap apart, then halves the gap to sort more finely. The gap shrinks 4 → 2 → 1.

🔒

🚀Start Shell Sort

Shell Sort

Definition

Key Characteristics

Time Complexity

🚀Start Shell Sort

Shell Sort

Definition

Key Characteristics

Time Complexity