# Shell Sort in Python | Implementation

This tutorial will teach you how to implement Shell Sort on a list of numbers using Python.

I am sure you must be quite familiar with Insertion Sort. If not, you can check out the link below:-

How to perform Insertion Sort in Python ?

So, Shell Sort is nothing but a variation of Insertion Sort. The main difference lies in the fact that in Insertion Sort, we shift elements by only one position. But, in Shell Sort, we shift elements by more than one position in one go.

In Shell Sort, we make the list n-sorted for a large value of n. Then we repeatedly decrement the value of n up until n becomes 1. When this happens, our list is sorted.

So, now that we know what Shell Sort is and how it works, let’s begin.

## Python Code: Shell sort

```def Shell(a):

# We count the length and then start with a large interval

length = len(a)
interval = int(length/2)

'''
We perform insertion sort on this large interval.
Then, we reduce the interval again and again using a while loop.
'''

while (interval > 0):

# Insertion Sort

for i in range(interval,length):

temp = a[i]

j = i
while(j >= interval and a[j - interval] > temp):
a[j] = a[j-interval]
j -= interval

a[j] = temp

# Making interval smaller

interval = int(interval/2)

# Main Function

if __name__=="__main__":

print("Enter a list of numbers seperated by a space :- ")

ip = list(map(int,input().split()))

print ("Original List :- ")

for i in range(len(ip)):
print(ip[i]),

Shell(ip)

print ("\nList After Sorting :- ")

for i in range(len(ip)):
print(ip[i])```

In the main function, first, we take a list of numbers as input from the user. Then, we call the Shell function to begin the process of Shell Sort.

In the Shell function, we first create a big interval equal to half of the list. Then we enter a while loop and then repeatedly perform Insertion Sort until the interval becomes zero. We decrease the value of the interval before the beginning of each iteration.

#### OUTPUT

```Enter a list of numbers seperated by a space :-

7 18 1 45 6 9 100 0
Original List :-
7
18
1
45
6
9
100
0

List After Sorting :-
0
1
6
7
9
18
45
100```

#### ANALYSIS OF SHELL SORT

In this implementation of Shell Sort, the time complexity is O(n^2). Although it is the same as Insertion Sort, it performs better when it comes to real-life scenarios when we have to swap elements that are very far away.