"""Experiment 4: how many comparisons does Python's built-in sort make? O(n log n).

We shuffle a list (same shuffle every run, so results repeat), then count
every comparison sorted() makes. We compare the count with n log2 n and n².
"""
import functools
import math
import random

from common import save

SIZES = [1_000, 10_000, 100_000]


def count_sort_comparisons(items):
    count = 0

    def compare(a, b):
        nonlocal count
        count += 1
        return (a > b) - (a < b)

    result = sorted(items, key=functools.cmp_to_key(compare))
    assert result == sorted(items)
    return count


def main():
    results = []
    print(f"{'items':>8} | {'comparisons':>12} | {'n log2 n':>12} | {'n squared':>16}")
    for n in SIZES:
        items = list(range(n))
        random.Random(42).shuffle(items)
        comparisons = count_sort_comparisons(items)
        n_log_n = round(n * math.log2(n))
        print(f"{n:>8,} | {comparisons:>12,} | {n_log_n:>12,} | {n * n:>16,}")
        results.append({
            "n": n,
            "comparisons": comparisons,
            "n_log2_n": n_log_n,
            "n_squared": n * n,
        })

    save("exp4", results)


if __name__ == "__main__":
    main()