import time
import random
import matplotlib.pyplot as plt

def merge(arr, l, m, r):
    n1 = m - l + 1
    n2 = r - m
    L = [0] * n1
    R = [0] * n2

    for i in range(n1):
        L[i] = arr[l + i]
    for j in range(n2):
        R[j] = arr[m + 1 + j]

    i = 0
    j = 0
    k = l

    while i < n1 and j < n2:
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
        k += 1

    while i < n1:
        arr[k] = L[i]
        i += 1
        k += 1

    while j < n2:
        arr[k] = R[j]
        j += 1
        k += 1

def mergeSort(arr, l, r):
    if l < r:
        m = l + (r - l) // 2
        mergeSort(arr, l, m)
        mergeSort(arr, m + 1, r)
        merge(arr, l, m, r)

def measure_time(n):
    arr = [random.randint(0, 10000) for _ in range(n)]
    start_time = time.time()
    mergeSort(arr, 0, len(arr) - 1)
    end_time = time.time()
    return end_time - start_time

# Experiment with different values of n
n_values = [100, 500, 1000, 5000, 10000, 20000, 50000]
times = []

for n in n_values:
    t = measure_time(n)
    times.append(t)
    print(f"Time taken to sort {n} elements: {t:.6f} seconds")

# Plotting the graph
plt.plot(n_values, times, marker='o')
plt.xlabel('Number of elements (n)')
plt.ylabel('Time taken (seconds)')
plt.title('Merge Sort Time Complexity')
plt.grid(True)
plt.show()