``````"""
https://en.wikipedia.org/wiki/Shellsort#Pseudocode
"""

def shell_sort(collection):
"""Pure implementation of shell sort algorithm in Python
:param collection:  Some mutable ordered collection with heterogeneous
comparable items inside
:return:  the same collection ordered by ascending

>>> shell_sort([0, 5, 3, 2, 2])
[0, 2, 2, 3, 5]
>>> shell_sort([])
[]
>>> shell_sort([-2, -5, -45])
[-45, -5, -2]
"""
# Marcin Ciura's gap sequence

gaps = [701, 301, 132, 57, 23, 10, 4, 1]
for gap in gaps:
for i in range(gap, len(collection)):
insert_value = collection[i]
j = i
while j >= gap and collection[j - gap] > insert_value:
collection[j] = collection[j - gap]
j -= gap
if j != i:
collection[j] = insert_value
return collection

if __name__ == "__main__":
from doctest import testmod

testmod()
user_input = input("Enter numbers separated by a comma:\n").strip()
unsorted = [int(item) for item in user_input.split(",")]
print(shell_sort(unsorted))
``````

#### Problem Statement

Given an unsorted array of n elements, write a function to sort the array

#### Approach

• go through the first (n - g) elements in the array
• compare the element with the next element that is g distance away
• swap the two elements if the first element is bigger
• decrease the gap and repeat until gap = 1

#### Time Complexity

Time complexity is dependent on the gap sequences. Below time complexities are based on the gap sequences of n/2^k.

`O(n^2)` Worst case performance

`O(n)` Best-case performance

`O(n^2)` Average performance

#### Space Complexity

`O(1)` Worst case

Donald Shell

#### Example

``````arr[] = {61, 109, 149, 111, 34, 2, 24, 119}
Initial Gap: 4

1.  Index = 0, Next element index = 4
2.  61 > 34, swap 61 and 34
3.  The array is now {34, 109, 149, 111, 61, 2, 24, 119}

4.  Index = 1, Next element index = 5
5.  109 > 2, swap 109 and 2
6.  The array is now {34, 2, 149, 111, 61, 109, 24, 119}

7.  Index = 2, Next element index = 6
8.  149 > 24, swap 149 and 24
9.  The array is now {34, 2, 24, 111, 61, 109, 149, 119}

10. Index = 3, Next element index = 7
11. 111 < 119, do nothing and continue

12. Divide the gap by 2 and repeat until gap = 1
``````

#### Video Explanation

A video explaining the Shell Sort Algorithm

#### Others

Shell sort is also known as diminishing increment sort.  