Lb2

hlyakhtin_Maksim_lb2/src/main.py
@@ -0,0 +1,86 @@
def calcMinRun(n):
    r = 0
    while n >= 64:
        r |= n & 1
        n >>= 1
    return n + r


def cmp(a, b):
    if a ** 2 < b ** 2 or a ** 2 == b ** 2 and a > b:
        return True
    return False


def insertion_sort(arr, left, right):
    if len(arr) <= 1:
        return

    for i in range(left + 1, right):
        j = i
        while j > left and cmp(arr[j], arr[j - 1]):
            arr[j], arr[j - 1] = arr[j - 1], arr[j]
            j -= 1


def merge_sort(arr):
    if len(arr) == 1 or len(arr) == 0:
        return arr

    arr_l = merge_sort(arr[:len(arr) // 2])
    arr_r = merge_sort(arr[len(arr) // 2:])
    res_arr = [0] * (len(arr_l) + len(arr_r))

    arr_l_count = 0
    arr_r_count = 0
    res_count = 0

    while arr_r_count < len(arr_r) and arr_l_count < len(arr_l):
        if arr_l[arr_l_count] ** 2 < arr_r[arr_r_count] ** 2:
            res_arr[res_count] = arr_l[arr_l_count]
            arr_l_count += 1
        elif arr_l[arr_l_count] ** 2 > arr_r[arr_r_count] ** 2:
            res_arr[res_count] = arr_r[arr_r_count]
            arr_r_count += 1
        elif arr_l[arr_l_count] ** 2 == arr_r[arr_r_count] ** 2:
            if arr_l[arr_l_count] >= arr_r[arr_r_count]:
                res_arr[res_count] = arr_l[arr_l_count]
                arr_l_count += 1
            else:
                res_arr[res_count] = arr_r[arr_r_count]
                arr_r_count += 1
        res_count += 1
    while arr_l_count < len(arr_l):
        res_arr[res_count] = arr_l[arr_l_count]
        arr_l_count += 1
        res_count += 1
    while arr_r_count < len(arr_r):
        res_arr[res_count] = arr_r[arr_r_count]
        arr_r_count += 1
        res_count += 1
    for i in range(len(res_arr)):
        arr[i] = res_arr[i]
    return arr


def timsort(arr, minRun=32):
    n = len(arr)

    i = 0
    for start in range(0, n, minRun):
        end = min(start + minRun, n)
        insertion_sort(arr, start, end)

        if start != end:
            print(f"Part {i}:", *arr[start:end])
        else:
            print(f"Part {i}:", arr[start])
        i += 1
    merge_sort(arr)


n = int(input())
arr = list(map(int, input().split()))
timsort(arr)
print("Answer:", *arr)