---

import time
import random


def bubble(a):
    a = a[:]
    n = len(a)
    for i in range(n):
        for j in range(n - 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
    left = merge(a[:m])
    right = merge(a[m:])
    res = []
    i = 0
    j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            res.append(left[i])
            i += 1
        else:
            res.append(right[j])
            j += 1
    res.extend(left[i:])
    res.extend(right[j:])
    return res


def timeit(func, a, repeats=3):
    times = []
    for _ in range(repeats):
        start = time.perf_counter()
        func(a)
        times.append(time.perf_counter() - start)
    return sum(times) / repeats


def table(headers, rows):
    widths = []
    for i in range(len(headers)):
        w = len(str(headers[i]))
        for row in rows:
            if len(str(row[i])) > w:
                w = len(str(row[i]))
        widths.append(w)

    line = "+"
    for w in widths:
        line += "-" * (w + 2) + "+"

    print(line)
    header_line = "|"
    for i in range(len(headers)):
        header_line += " " + str(headers[i]).ljust(widths[i]) + " |"
    print(header_line)
    print(line.replace("-", "="))

    for row in rows:
        row_line = "|"
        for i in range(len(row)):
            row_line += " " + str(row[i]).ljust(widths[i]) + " |"
        print(row_line)
    print(line)


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

if choice == '1':
    data = input("Числа через пробел: ")
    arr = []
    for x in data.split():
        arr.append(int(x))
elif choice == '2':
    filename = input("Файл: ")
    with open(filename) as f:
        text = f.read().replace(",", " ")
    arr = []
    for x in text.split():
        arr.append(int(x))
else:
    n = int(input("Размер: "))
    arr = []
    for _ in range(n):
        arr.append(random.randint(-1000, 1000))

assert bubble(arr) == merge(arr) == sorted(arr), "Ошибка сортировки!"

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

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