"""BTVN: sắp xếp trộn, Python3; dữ liệu số nguyên tự tạo.

python3 g11-cs-sap-xep-tron.py tron g11-cs-tron-hai-day.inp Data.out
python3 g11-cs-sap-xep-tron.py sap g11-cs-day-can-sap-xep.inp
python3 g11-cs-sap-xep-tron.py truc-tiep g11-cs-day-can-sap-xep.inp
python3 g11-cs-sap-xep-tron.py do g11-cs-day-can-sap-xep.inp --repeat 100
Đọc tệp trước đoạn đo; hai thuật toán nhận bản sao của cùng dãy gốc.
"""
import argparse
from pathlib import Path
from time import perf_counter


def merge(B, C):
    m, n = len(B), len(C)
    A = [0] * (m + n)
    i = j = k = 0
    while i < m and j < n:
        if B[i] <= C[j]:
            A[k] = B[i]
            i += 1
        else:
            A[k] = C[j]
            j += 1
        k += 1
    while i < m:
        A[k] = B[i]
        i += 1
        k += 1
    while j < n:
        A[k] = C[j]
        j += 1
        k += 1
    return A


def mergeSort(A):
    if len(A) <= 1:
        return A
    k = len(A) // 2
    B = mergeSort(A[:k])
    C = mergeSort(A[k:])
    return merge(B, C)


def insertionSort(A):
    for i in range(1, len(A)):
        value = A[i]
        j = i - 1
        while j >= 0 and A[j] > value:
            A[j + 1] = A[j]
            j -= 1
        A[j + 1] = value


def merge_into(A, left, mid, right):
    # Hai đoạn đã sắp xếp; dãy phụ chỉ lớn bằng đoạn đang trộn.
    B = [0] * (right - left + 1)
    i, j, k = left, mid + 1, 0
    while i <= mid and j <= right:
        if A[i] <= A[j]:
            B[k] = A[i]
            i += 1
        else:
            B[k] = A[j]
            j += 1
        k += 1
    while i <= mid:
        B[k] = A[i]
        i += 1
        k += 1
    while j <= right:
        B[k] = A[j]
        j += 1
        k += 1
    A[left:right + 1] = B


def mergeSort_into(A, left, right):
    if left < right:
        mid = (left + right) // 2
        mergeSort_into(A, left, mid)
        mergeSort_into(A, mid + 1, right)
        merge_into(A, left, mid, right)


def read_array(filename):
    return [int(x) for x in Path(filename).read_text(encoding='utf-8').split()]


def read_two(filename):
    with open(filename, encoding='utf-8') as source:
        first, second = source.readline(), source.readline()
        if first == '' or second == '' or source.read().strip():
            raise ValueError('Tệp cần đúng hai dòng dữ liệu; dòng trắng biểu diễn dãy rỗng.')
    B, C = [int(x) for x in first.split()], [int(x) for x in second.split()]
    if any(A[i] > A[i + 1] for A in [B, C] for i in range(len(A) - 1)):
        raise ValueError('Cả hai dãy cần không giảm trước khi trộn.')
    return B, C


def write_array(filename, A):
    Path(filename).write_text(' '.join(map(str, A)) + '\n', encoding='utf-8')


def benchmark(A, repeat):
    if not 1 <= repeat <= 1000 or len(A) > 5000:
        raise ValueError('Số lần đo từ 1 đến 1000; mỗi dãy tối đa 5000 phần tử.')
    expected = sorted(A)
    totals = [0.0, 0.0]
    for _ in range(repeat):
        B, C = A.copy(), A.copy()
        start = perf_counter()
        result = mergeSort(B)
        totals[0] += perf_counter() - start
        start = perf_counter()
        insertionSort(C)
        totals[1] += perf_counter() - start
        if result != expected or C != expected:
            raise AssertionError('Hai kết quả sắp xếp chưa khớp.')
    return [total * 1000 / repeat for total in totals]


def main():
    parser = argparse.ArgumentParser(description=__doc__)
    modes = parser.add_subparsers(dest='mode', required=True)
    combine = modes.add_parser('tron')
    combine.add_argument('input')
    combine.add_argument('output')
    for mode in ['sap', 'truc-tiep', 'do']:
        sub = modes.add_parser(mode)
        sub.add_argument('input')
        if mode == 'do':
            sub.add_argument('--repeat', type=int, default=100)
    args = parser.parse_args()
    try:
        if args.mode == 'tron':
            if Path(args.input).resolve() == Path(args.output).resolve():
                raise ValueError('Chọn tệp kết quả khác tệp dữ liệu gốc.')
            B, C = read_two(args.input)
            result = merge(B, C)
            write_array(args.output, result)
            print(' '.join(map(str, result)))
        else:
            A = read_array(args.input)
            if args.mode == 'sap':
                print(' '.join(map(str, mergeSort(A))))
            elif args.mode == 'truc-tiep':
                mergeSort_into(A, 0, len(A) - 1)
                print(' '.join(map(str, A)))
            else:
                timings = benchmark(A, args.repeat)
                print('n,so_lan,tron_ms_moi_lan,chen_ms_moi_lan')
                print(f'{len(A)},{args.repeat},{timings[0]:.9f},{timings[1]:.9f}')
    except (OSError, ValueError) as error:
        parser.exit(2, f'Dữ liệu không phù hợp: {error}\n')


if __name__ == '__main__':
    main()