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


def shell_sort(collection: list[int]) -> list[int]:
    """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

• start with the initial gap, g
• 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

Founder's Name

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.