import random
import time
import statistics
import numpy as np
import matplotlib.pyplot as plt

def timsort_builtin(arr):
    arr.sort()

def quicksort_naive(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr)//2]
    left  = [x for x in arr if x < pivot]
    mid   = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort_naive(left) + mid + quicksort_naive(right)

INSERTION_CUTOFF = 16

def _insertion_sort_range(a, lo, hi):
    for i in range(lo+1, hi+1):
        x = a[i]
        j = i - 1
        while j >= lo and a[j] > x:
            a[j+1] = a[j]
            j -= 1
        a[j+1] = x

def _median_of_three(a, i, j, k):
    ai, aj, ak = a[i], a[j], a[k]
    if ai < aj:
        if aj < ak:
            return j
        elif ai < ak:
            return k
        else:
            return i
    else:
        if ai < ak:
            return i
        elif aj < ak:
            return k
        else:
            return j

def quicksort_inplace(arr):
    a = arr
    if len(a) < 2:
        return
    stack = [(0, len(a)-1)]
    while stack:
        lo, hi = stack.pop()
        while hi - lo + 1 > INSERTION_CUTOFF:
            m = lo + (hi - lo)//2
            piv_idx = _median_of_three(a, lo, m, hi)
            a[piv_idx], a[hi] = a[hi], a[piv_idx]
            pivot = a[hi]
            i = lo - 1
            for j in range(lo, hi):
                if a[j] <= pivot:
                    i += 1
                    a[i], a[j] = a[j], a[i]
            i += 1
            a[i], a[hi] = a[hi], a[i]
            left_len = i - 1 - lo + 1
            right_len = hi - (i + 1) + 1
            if left_len < right_len:
                if i + 1 < hi:
                    stack.append((i+1, hi))
                hi = i - 1
            else:
                if lo < i - 1:
                    stack.append((lo, i-1))
                lo = i + 1
        _insertion_sort_range(a, lo, hi)

def mergesort_py(arr):
    n = len(arr)
    if n <= 1:
        return arr
    mid = n // 2
    left = mergesort_py(arr[:mid])
    right = mergesort_py(arr[mid:])
    i = j = 0; out = []
    nl, nr = len(left), len(right)
    while i < nl and j < nr:
        if left[i] <= right[j]:
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    if i < nl: out.extend(left[i:])
    if j < nr: out.extend(right[j:])
    return out

def numpy_quicksort(arr):
    np.sort(arr, kind="quicksort")

def time_func(fn, data, repeats=5, as_inplace=False, preconvert=None):
    times = []
    for _ in range(repeats):
        if preconvert == "numpy":
            x = np.array(data, dtype=np.int64)
        else:
            x = list(data)
        start = time.perf_counter()
        if as_inplace:
            fn(x)
        else:
            _ = fn(x)
        times.append(time.perf_counter() - start)
    import statistics
    return statistics.median(times)

def main():
    sizes = [1_000, 5_000, 10_000, 20_000]
    algs = [
        ("Timsort (list.sort)", lambda a: timsort_builtin(a), True, None),
        ("QuickSort naive (Py)", quicksort_naive, False, None),
        ("QuickSort in-place (Py, Mo3+Ins)", lambda a: quicksort_inplace(a), True, None),
        ("MergeSort (Py)", mergesort_py, False, None),
        ("NumPy quicksort", lambda a: numpy_quicksort(a), True, "numpy"),
    ]

    results = {name: [] for name, *_ in algs}

    for n in sizes:
        data = [random.randint(0, 10_000_000) for _ in range(n)]
        for name, fn, inplace, pre in algs:
            t = time_func(fn, data, repeats=5, as_inplace=inplace, preconvert=pre)
            results[name].append(t)

    import matplotlib.pyplot as plt
    plt.figure(figsize=(8,5))
    for name, vals in results.items():
        plt.plot(sizes, vals, marker='o', label=name)
    plt.xlabel("Array size (n)")
    plt.ylabel("Time (seconds)")
    plt.yscale("log")
    plt.title("Python vs NumPy: Sorting Performance (median of 5 runs)")
    plt.legend()
    plt.grid(True)
    plt.show()

if __name__ == "__main__":
    main()