algorithms/algorithms/sort/shell_sort.py at master · pk210700/algorithms · GitHub

Repository navigation

21 lines (19 loc) · 542 Bytes

def shell_sort(arr):

''' Shell Sort

Complexity: O(n^2)

'''

n = len(arr)

# Initialize size of the gap

gap = n//2

while gap > 0:

y_index = gap

while y_index < len(arr):

y = arr[y_index]

x_index = y_index - gap

while x_index >= 0 and y < arr[x_index]:

arr[x_index + gap] = arr[x_index]

x_index = x_index - gap

arr[x_index + gap] = y

y_index = y_index + 1

gap = gap//2

return arr