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()
Click Run or press shift + ENTER to run code