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

def merge(left, right):
    """Merge two sorted lists."""
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

def merge_sort(arr):
    """Perform merge sort on the array."""
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def measure_time(n):
    """Generate random numbers and measure the time taken to sort them."""
    arr = np.random.randint(0, 1000000, size=n)
    start_time = time.time()
    sorted_arr = merge_sort(arr)  # Use single-threaded merge sort
    end_time = time.time()
    return end_time - start_time

# Experiment with different values of n
n_values = [1000, 5000, 10000, 50000, 100000, 500000]
times = []

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

# Plotting the results
plt.figure(figsize=(10, 6))
plt.plot(n_values, times, marker='o')
plt.title('Time taken to sort elements vs Number of elements')
plt.xlabel('Number of elements (n)')
plt.ylabel('Time taken (seconds)')
plt.xscale('log')
plt.yscale('log')
plt.grid(True)
plt.show()