# Interview essential algorithm ｜ graphic Hill sorting (Python)

#### Shell Sort

Hill's idea of sequencing

​ Hill sort is an improved method of insertion sort , It divides the original list into countless sub lists , Then insert sort is performed on each sub list , The key to Hill sorting is to control the step size （ It can be seen as taking elements as sub lists every few elements ）.

Graphic Hill sort

​ Given the following list ：

​ We use 2 As step size （ Take an element every two characters ）, It can be divided into three sub lists as follows .

​ With three sub lists , We insert and sort the three sub lists respectively

​ According to the above figure, we can find that the combination results we obtained are not completely sorted successfully , Finally, we need to do an insert sort on the list .

​ So our Hill sorting is complete .

The nature of Hill sort

• Optimal time complexity ： O ( n ) O(n)
• Worst time complexity ： O ( n 2 ) O(n^2)
• stability ： unstable
• Compare insert sort ： By changing the increment, the time complexity will be optimized .

Hill sort code implementation

lst = list(map(int, input().split(',')))
def shell_sort(alist):
n = len(alist)
gap = n // 2
while gap > 0:
for i in range(gap, n):
j = i
while j >= gap:
if alist[j] < alist[j - gap]:
alist[j], alist[j - gap] = alist[j - gap], alist[j]
j -= gap
else:
break
gap //= 2
return alist
shell_sort(lst)