---

import time
import random


def bubble(a):
    a = a[:]
    for i in range(len(a)):
        for j in range(len(a) - i - 1):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
    return a


def merge(a):
    if len(a) <= 1:
        return a
    m = len(a) // 2
    l, r = merge(a[:m]), merge(a[m:])
    res, i, j = [], 0, 0
    while i < len(l) and j < len(r):
        if l[i] <= r[j]:
            res.append(l[i]); i += 1
        else:
            res.append(r[j]); j += 1
    return res + l[i:] + r[j:]


def timeit(f, a, n=3):
    t = []
    for _ in range(n):
        s = time.perf_counter()
        f(a)
        t.append(time.perf_counter() - s)
    return sum(t) / n


def table(headers, rows):
    w = [max(len(str(h)), *(len(str(r[i])) for r in rows)) for i, h in enumerate(headers)]
    line = '+' + '+'.join('-' * (x + 2) for x in w) + '+'
    fmt = lambda r: '|' + '|'.join(f' {str(c):<{w[i]}} ' for i, c in enumerate(r)) + '|'
    print(line)
    print(fmt(headers))
    print(line.replace('-', '='))
    for r in rows:
        print(fmt(r))
    print(line)


# --- ввод ---
print("1 - вручную, 2 - из файла, 3 - случайно")
c = input("Выбор: ")

if c == '1':
    a = [int(x) for x in input("Числа через пробел: ").split()]
elif c == '2':
    a = [int(x) for x in open(input("Файл: ")).read().replace(',', ' ').split()]
else:
    a = [random.randint(-1000, 1000) for _ in range(int(input("Размер: ")))]

# --- проверка и замер ---
assert bubble(a) == merge(a) == sorted(a), "Ошибка сортировки!"

tb, tm = timeit(bubble, a), timeit(merge, a)

# --- вывод ---
print(f"\nЭлементов: {len(a)}")
table(
    ["Алгоритм", "Время (с)", "Сложность"],
    [
        ["Пузырьковая", f"{tb:.6f}", "O(n^2)"],
        ["Слиянием",    f"{tm:.6f}", "O(n log n)"],
    ]
)
print(f"\nСлияние быстрее в {tb / tm:.1f} раз(а)")