---

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 show(arr, label, limit=20):
    if len(arr) <= limit:
        body = str(arr)
    else:
        body = str(arr[:limit]) + f" ... (всего {len(arr)})"
    return label + ":\n  " + body


def render_table(headers, rows, title=None):
    """Возвращает таблицу строкой (не печатает)."""
    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) + "+"

    out = []
    if title:
        total = sum(widths) + 3 * len(widths) - 1
        out.append("=" * total)
        out.append(title.center(total))
        out.append("=" * total)

    out.append(line)

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

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

    out.append(line)
    return "\n".join(out)


def read_arrays_from_file(filename):
    """Читает файл, где каждая строка — отдельный массив."""
    arrays = []
    with open(filename, encoding="utf-8") as f:
        for line in f:
            line = line.strip().replace(",", " ")
            if not line:
                continue
            arr = []
            for x in line.split():
                arr.append(int(x))
            arrays.append(arr)
    return arrays


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

if choice == '1':
    data = input("Числа через пробел: ")
    arr = []
    for x in data.split():
        arr.append(int(x))
    arrays = [arr]
    names = ["Массив 1"]

elif choice == '2':
    filename = input("Файл: ")
    arrays = read_arrays_from_file(filename)
    names = []
    for i in range(len(arrays)):
        names.append(f"Массив {i + 1}")

else:
    count = int(input("Сколько массивов: "))
    arrays = []
    names = []
    for i in range(count):
        n = int(input(f"Размер массива {i + 1}: "))
        arr = []
        for _ in range(n):
            arr.append(random.randint(-1000, 1000))
        arrays.append(arr)
        names.append(f"Массив {i + 1} (n={n})")

# ---------- ОБРАБОТКА ----------
report = []          # сюда копим весь отчёт
rows = []            # строки итоговой таблицы

for idx in range(len(arrays)):
    arr = arrays[idx]
    name = names[idx]

    # проверка корректности
    assert bubble(arr) == merge(arr) == sorted(arr), f"Ошибка сортировки в {name}"

    tb = timeit(bubble, arr)
    tm = timeit(merge, arr)
    ratio = tb / tm if tm > 0 else float('inf')

    # блок с массивами
    report.append("=" * 60)
    report.append(name)
    report.append("=" * 60)
    report.append(show(arr, "Исходный массив"))
    report.append(show(bubble(arr), "После пузырьковой"))
    report.append(show(merge(arr), "После слиянием"))
    report.append("")

    # строка таблицы
    rows.append([
        name,
        len(arr),
        f"{tb:.6f}",
        f"{tm:.6f}",
        f"{ratio:.1f}x",
    ])

# итоговая таблица
headers = ["Массив", "N", "Пузырьковая (с)", "Слиянием (с)", "Быстрее"]
summary = render_table(headers, rows, title="Итоговая таблица")

report.append("")
report.append(summary)

text = "\n".join(report)

# ---------- ВЫВОД ----------
print()
print(text)

# сохранить в файл
out_name = input("\nИмя файла для сохранения (Enter — report.txt): ").strip()
if not out_name:
    out_name = "report.txt"

with open(out_name, "w", encoding="utf-8") as f:
    f.write(text)

print(f"Отчёт сохранён в: {out_name}")