s1_name = "вставками"
def simple_sort_1(A):
    for i in range(1, len(A)):
        j = A[i]
        k = i - 1
        while k >= 0 and A[k] > j:
            A[k+1] = A[k]
            k -= 1
        A[k+1] = j
    return  A


s2_name = "эффективный пузырек"
def simple_sort_2(A):
    for i in range(len(A) - 1):
        Check = True
        for j in range(len(A) - i - 1):
            if A[j] > A[j+1]:
                A[j], A[j + 1] = A[j + 1], A[j]
                Check = False
        if Check:
            break
    return A


s3_name = "расческой"
def simple_sort_3(A):
    gap = (len(A) * 10 // 13) if len(A) > 1 else 0
    while gap:
        if 8 < gap < 11:
            gap = 11
        swapped = False
        for i in range(len(A) - gap):
            if A[i + gap] < A[i]:
                A[i], A[i + gap] = A[i + gap], A[i]
                swapped = True
        gap = (gap * 10 // 13) or swapped
    return A

s4_name = "шейкерная"
def simple_sort_4(A):
    left = 0
    right = len(A) - 1

    while left <= right:
        for i in range(left, right, +1):
            if A[i] > A[i + 1]:
                A[i], A[i + 1] = A[i + 1], A[i]
        right -= 1

        for i in range(right, left, -1):
            if A[i - 1] > A[i]:
                A[i], A[i - 1] = A[i - 1], A[i]
        left += 1
    return A
def merge(A, left, mid, right):
    i = left
    j = mid + 1
    AUX = []
    while i <= mid and j <= right:
        if A[i] < A[j]:
            AUX.append(A[i])
            i += 1
        else:
            AUX.append(A[j])
            j += 1

    for k in range(i, mid + 1):
        AUX.append(A[k])

    for k in range(j, right + 1):
        AUX.append(A[k])
    A[left:right + 1] = AUX
    return A


def mergeSortRec(A, left, right):
    if left >= right:
        return A
    mid = (left + right) // 2
    A = mergeSortRec(A, left, mid)
    A = mergeSortRec(A, mid + 1, right)
    A = merge(A, left, mid, right)
    return A

es_name = "слиянием"
def effective_sort(A):
    result = mergeSortRec(A, 0, len(A) - 1)
    return A



def shell_sort(A):
    gaps = [701, 301, 132, 57, 23, 10, 4, 1]
    for step in gaps:
        for i in range(len(A)):
            elem = A[i]
            index = i
            while index >= step and elem < A[index - step]:
                A[index] = A[index - step]
                index = index - step
            A[index] = elem
    return A