Algorithm Guidecomplexity: O(n log² n)

Shell Sort

A generalization of insertion sort that repeats gapped insertion while progressively shrinking the gap, moving distant elements efficiently. Performance hinges on the gap sequence.

01 Explore How It Works

Interactive Step-by-Step

HOVER OR SCROLL

Shell Sort · gap=4→2→1

쉘 정렬을 시작합니다. 간격(gap)을 줄여가며 간격을 둔 삽입 정렬을 반복합니다. n=8, gap = n/2 = 4.

Logic Node1 / 13

Live Python

1def shell_sort(arr):

# n: 8

2 n = len(arr)

# gap: 4

3 gap = n // 2

4 while gap > 0:

5 for i in range(gap, n):

6 temp = arr[i]

7 j = i

8 while j >= gap and arr[j - gap] > temp:

9 arr[j] = arr[j - gap]

10 j -= gap

11 arr[j] = temp

12 gap //= 2

13 return arr

02 Understand It Simply

For Everyone

🔑Analogy

Roughly align far-apart cards first, then tidy up more finely as the gap narrows.

💡In Plain Words

Sorts elements spaced by a gap first, then reduces the gap to finish.

A big improvement over plain insertion sort.

📍Where It's Used

–Medium-sized data
–memory-constrained environments

03 Python Implementation

A clean, readable reference implementation of the core logic of Shell Sort.

core_implementation.py

def shell_sort(arr):
    n = len(arr)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 2
    return arr

04 Frequently Asked Questions

FAQ

What is Shell Sort?+

A generalization of insertion sort that repeats gapped insertion while progressively shrinking the gap, moving distant elements efficiently. Performance hinges on the gap sequence.

What is the time complexity of Shell Sort?+

The time complexity of Shell Sort is O(n log² n). Follow the step-by-step visualization to see exactly why.

Where is Shell Sort used?+

Medium-sized data, memory-constrained environments.

What's a simple analogy for Shell Sort?+

Roughly align far-apart cards first, then tidy up more finely as the gap narrows.

→ Sorting — see allRelated