def shell(arr):
    gap = len(arr) // 2

    while gap > 0:
        for i in range(gap, len(arr)):
            current = arr[i]
            ind = i

            while ind >= gap and arr[ind - gap] > current:
                arr[ind] = arr[ind - gap]
                ind -= gap
                arr[ind] = current

        gap //= 2
    return arr


arr = [12, 74, 25, 14, 60, 28, 13, 5, 76]
print(arr)
result = shell(arr)
print(result)


def merge_cut(lst):
    if len(lst) <= 1:
        return lst
    middle = len(lst) // 2
    left = lst[:middle]
    right = lst[middle:]

    left = merge_cut(left)
    right = merge_cut(right)

    return list(merge(left, right))


def merge(left_half, right_half):
    res = []
    while len(left_half) != 0 and len(right_half) != 0:
        if left_half[0] < right_half[0]:
            res.append(left_half[0])
            left_half.remove(left_half[0])
        else:
            res.append(right_half[0])
            right_half.remove(right_half[0])
    if len(left_half) == 0:
        res += right_half
    else:
        res += left_half
    return res


lst = [12, 34, 25, 15, 67, 23, 11, 5, 86]
print(lst)
re = merge_cut(lst)
print(re)