"""Reproducible local comparison of Python sorted() and insertion sort."""

import csv
import platform
import random
import sys
import time
from pathlib import Path


OUT = Path(__file__).resolve().parent
SIZES = (100, 1000, 5000)
REPEATS = 7
SEED = 20261102


def insertion_sort(values):
    result = values.copy()
    for i in range(1, len(result)):
        key = result[i]
        j = i - 1
        while j >= 0 and result[j] > key:
            result[j + 1] = result[j]
            j -= 1
        result[j + 1] = key
    return result


def make_data(size, distribution, rng):
    values = [rng.randrange(0, 1_000_000) for _ in range(size)]
    if distribution == "nearly_sorted":
        values.sort()
        swaps = max(1, size // 100)
        for _ in range(swaps):
            a, b = rng.randrange(size), rng.randrange(size)
            values[a], values[b] = values[b], values[a]
    return values


def main():
    rng = random.Random(SEED)
    rows = []
    for distribution in ("random", "nearly_sorted"):
        for size in SIZES:
            source = make_data(size, distribution, rng)
            expected = sorted(source)
            for algorithm, function in (("builtin_sorted", sorted), ("insertion_sort", insertion_sort)):
                for repeat in range(1, REPEATS + 1):
                    started = time.perf_counter()
                    result = function(source)
                    elapsed = time.perf_counter() - started
                    if result != expected:
                        raise AssertionError(f"Output mismatch: {distribution=}, {size=}, {algorithm=}")
                    rows.append({
                        "distribution": distribution,
                        "size": size,
                        "algorithm": algorithm,
                        "repeat": repeat,
                        "elapsed_seconds": f"{elapsed:.9f}",
                        "correct": True,
                    })

    csv_path = OUT / "sort_benchmark_timings.csv"
    with csv_path.open("w", newline="", encoding="utf-8-sig") as stream:
        writer = csv.DictWriter(stream, fieldnames=rows[0].keys())
        writer.writeheader()
        writer.writerows(rows)

    grouped = {}
    for row in rows:
        key = (row["distribution"], row["size"], row["algorithm"])
        grouped.setdefault(key, []).append(float(row["elapsed_seconds"]))
    print(f"Python: {sys.version.split()[0]} ({platform.python_implementation()})")
    print(f"Platform: {platform.platform()}")
    print(f"Seed: {SEED}; repeats: {REPEATS}; rows: {len(rows)}")
    print("distribution,size,algorithm,median_seconds,min_seconds,max_seconds")
    for key, times in grouped.items():
        ordered = sorted(times)
        median = ordered[len(ordered) // 2]
        print(f"{key[0]},{key[1]},{key[2]},{median:.9f},{min(times):.9f},{max(times):.9f}")
    print(f"CSV: {csv_path}")


if __name__ == "__main__":
    main()