import random
import time
from tqdm import tqdm
'''
def shell_sort(arr):
    n = len(arr)
    h = n // 2
    
    while h >= 1:
        for k in range(h):
            for i in range(k + h, n):
                s = arr[i]
                j = i - h
                while j >= 0 and s < arr[j]:
                    arr[j + h] = arr[j]
                    j -= h
                arr[j + h] = s
        h //= 2
'''
def shell_sort(ll):
    n = len(ll)
    d = n // 2 # шаг
    while d > 0:
        for i in range(d, n):
            j, t = i, ll[i]
            while j >= d and ll[j -d] > t:
                ll[j] = ll[j - d]
                j -= d
            ll[j] = t
        d //= 2
    return ll

def bubble_sort(arr):
    print('Отсортированный массив методом пузырька:')
    n = len(arr)
    for i in tqdm(range(n - 1)):
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr


def insert_sort(arr):
    print('Отсортированный массив методом вставок:')
    n = len(arr)
    for i in tqdm(range(1, n)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr


def choice_sort(arr):
    print('Отсортированный массив методом выбора:')
    n = len(arr)
    for i in tqdm(range(n - 1)):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

def print_array(arr):
    print(' '.join(map(str, arr)))


def copy_array(source):
    return source.copy()


def input_array_console():
    n = int(input('Задайте длину массива: '))
    if n >= 0:
        arr = []
        print('Задайте элементы массива: ')
        for i in range(n):
            arr.append(int(input()))
        print('Исходный массив:')
        print_array(arr)
        arr_shell = shell_sort(arr)
        print('Отсортированный массив методом Шелла:')
        print_array(arr_shell)
    else:
        print('Вы ввели некорректное значение длины массива')


def random_array(n):
    return [random.randint(0, 100) for _ in range(n)]


def analyze():
    size1 = int(input('Произведём анализ. Введите размер массива: '))
    print('Выберите тип массива:')
    print('1 - Уже отсортированный по возрастанию массив')
    print('2 - Массив со случайными значениями')
    print('3 - Обратно отсортированный массив')
    b = int(input())
    
    if b < 1 or b > 3:
        print('Введён некорректный номер')
        return

    if b == 1:
        array1_1 = list(range(size1))
    elif b == 2:
        array1_1 = random_array(size1)
    elif b == 3:
        array1_1 = list(range(size1 - 1, -1, -1))

    array1_2 = copy_array(array1_1)
    array1_3 = copy_array(array1_1)
    array1_4 = copy_array(array1_1)

    print('Исходный массив:')
    # print_array(array1_1)

    # Сортировка пузырьком
    start_time = time.time()
    bubble_sort(array1_2)
    elapsed_time = time.time() - start_time
    # print_array(array1_2)
    print('Время в миллисекундах:', elapsed_time * 1000)

    # Сортировка выбором
    start_time = time.time()
    choice_sort(array1_3)
    elapsed_time = time.time() - start_time
    # print_array(array1_3)
    print('Время в миллисекундах:', elapsed_time * 1000)

    # Сортировка вставками
    start_time = time.time()
    insert_sort(array1_4)
    elapsed_time = time.time() - start_time
    # print_array(array1_4)
    print('Время в миллисекундах:', elapsed_time * 1000)

    # Сортировка методом Шелла
    start_time = time.time()
    shell_sort(array1_1)
    elapsed_time = time.time() - start_time
    print('Отсортированный массив методом Шелла:')
    # print_array(array1_1)
    print('Время в миллисекундах:', elapsed_time * 1000)


if __name__ == "__main__":
    input_array_console()
    #analyze()

Используй numpy для ускорения