Shell Sort
A highly efficient, in-place comparison sort. It is an generalization of insertion sort, allowing the exchange of items that are far apart.
Visualization
Details
Analogy
Imagine sorting a large deck of cards. Instead of comparing adjacent cards, you first sort cards that are far apart (e.g., every 10th card). This gets cards roughly into position. You then decrease the 'gap' (e.g., sort every 5th card) and repeat, until finally you sort adjacent cards.
Purpose
To sort an array by starting with a large gap and gradually reducing it. For each gap, it performs an insertion sort on elements that are that far apart.
Use Cases
A good choice for medium-sized lists (up to a few thousand items). It's faster than simple O(n²) sorts but not as complex as O(n log n) sorts.
Algorithm Steps
gap = n / 2
while gap > 0:
for i = gap to n-1:
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
Explanation
What's Happening?
Initial array. Start with gap = 4.
Code Implementation
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