Mini Project
Name: Kiran Lalaso Narute Roll no: CO432 Class: BE COMP
Problem Statement: Implement merge sort and multithreaded merge sort.
Compare time required by both the algorithms. Also analyze the performance of
each algorithm for the best case and the worst case.
Program:
import time
import threading
import random
import sys
sys.setrecursionlimit(10**6)
# Merge Sort Implementation
def merge(arr, l, m, r):
n1 = m - l + 1
n2 = r - m
# Create temporary arrays
L = arr[l:l + n1]
R = arr[m + 1:m + 1 + n2]
# Merge the temp arrays back into arr[l..r]
i=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
# Copy the remaining elements of L[], if there are any
while i < n1:
arr[k] = L[i]
i += 1
k += 1
# Copy the remaining elements of R[], if there are any
while j < n2:
arr[k] = R[j]
j += 1
k += 1
def merge_sort(arr, l, r):
if l < r:
m = l + (r - l) // 2
merge_sort(arr, l, m)
merge_sort(arr, m + 1, r)
merge(arr, l, m, r)
# Multithreaded Merge Sort Implementation
def threaded_merge_sort(arr, l, r)
if l < r:
m = l + (r - l) // 2
# Creating threads for sorting two halves
left_thread = threading.Thread(target=threaded_merge_sort, args=(arr, l, m))
right_thread = threading.Thread(target=threaded_merge_sort, args=(arr, m + 1, r))
# Starting threads
left_thread.start()
right_thread.start()
# Joining threads to ensure they complete before merge
left_thread.join()
right_thread.join()
merge(arr, l, m, r)
# Helper function to measure execution time
def measure_time(sort_fn, arr, l, r):
start = time.time()
sort_fn(arr, l, r)
end = time.time()
return end - start
# Function to analyze performance for different cases
def analyze_performance():
sizes = [10**4, 10**5, 10**6]
for size in sizes:
# Best Case: Already sorted array
best_case_array = list(range(size))
# Worst Case: Reverse sorted array
worst_case_array = list(range(size, 0, -1))
# Random Case
random_case_array = [random.randint(0, 10000) for _ in range(size)]
print(f"\nAnalyzing for size: {size}")
# Standard Merge Sort
print("\nStandard Merge Sort:")
time_best = measure_time(merge_sort, best_case_array[:], 0, size - 1)
time_worst = measure_time(merge_sort, worst_case_array[:], 0, size - 1)
time_random = measure_time(merge_sort, random_case_array[:], 0, size - 1)
print(f"Best Case Time: {time_best:.4f} seconds")
print(f"Worst Case Time: {time_worst:.4f} seconds")
print(f"Random Case Time: {time_random:.4f} seconds")
# Multithreaded Merge Sort
print("\nMultithreaded Merge Sort:")
time_best_threaded = measure_time(threaded_merge_sort, best_case_array[:], 0, size - 1)
time_worst_threaded = measure_time(threaded_merge_sort, worst_case_array[:], 0, size - 1)
time_random_threaded = measure_time(threaded_merge_sort, random_case_array[:], 0, size - 1)
print(f"Best Case Time (Threaded): {time_best_threaded:.4f} seconds")
print(f"Worst Case Time (Threaded): {time_worst_threaded:.4f} seconds")
print(f"Random Case Time (Threaded): {time_random_threaded:.4f} seconds")
# Main function to run the performance analysis
if __name__ == "__main__":
analyze_performance()
Output:
PS C:\Users\HP\Desktop\python daa> & 'c:\Users\HP\AppData\Local\Programs\Python\Python311\python.exe'
'c:\Users\HP\.vscode\extensions\ms-python.debugpy-2024.10.0-win32-
x64\bundled\libs\debugpy\adapter/../..\debugpy\launcher' '51413' '--' 'c:\Users\HP\Desktop\python
daa\miniproject.py'
Analyzing for size: 10000
Standard Merge Sort:
Best Case Time: 0.0526 seconds
Worst Case Time: 0.0499 seconds
Random Case Time: 0.0700 seconds
Multithreaded Merge Sort:
Best Case Time (Threaded): 22.8297 seconds
Worst Case Time (Threaded): 20.1459 seconds
Random Case Time (Threaded): 32.0085 seconds
