from typing import Sequence
from typing import List


def shell_sort_iter(seq: Sequence) -> List:
    """
    Sort a sequence with the Shell sort algorithm.

    Parameters
    ----------
    seq : Sequence

    Returns
    -------
    List

    """
    seq = list(seq)  # copy -> purity sake
    size = len(seq)
    gap = size // 2
    while gap:
        for i in range(size):
            for j in range(i + gap, size, gap):
                if seq[i] > seq[j]:
                    seq[i], seq[j] = seq[j], seq[i]
        gap //= 2
    return seq