### A Bet Between Friends
Two friends, Alex and Taylor, were known for their friendly wagers on almost anything. One sunny afternoon, they found themselves disagreeing about the efficiency of a new sorting algorithm Taylor had read about. Alex claimed that the traditional QuickSort algorithm was more efficient in practice than the new one Taylor had in mind, MergeSort.
Taylor, confident in the new algorithm’s theoretical guarantees, proposed a bet. They would each write a program to sort a large list of random integers and compare the execution times. The person with the slower program would have to treat the other to dinner at their favorite restaurant.
With the bet settled, they got to work. Alex quickly wrote a QuickSort program, while Taylor implemented MergeSort. They decided to use the same list of 10,000 random integers for a fair comparison.
“`python
import random
import time
# QuickSort Algorithm
def quicksort(arr):
if len(arr) pivot]
return quicksort(left) + middle + quicksort(right)
# MergeSort Algorithm
def mergesort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = mergesort(arr[:mid])
right = mergesort(arr[mid:])
return merge(left, right)
def merge(left, right):
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
# Generate a list of 10,000 random integers between 1 and 100,000
random_list = [random.randint(1, 100000) for _ in range(10000)]
# Copy the list for fair comparison
list_for_quicksort = random_list.copy()
list_for_mergesort = random_list.copy()
# Measure the time taken by QuickSort
start_time = time.time()
sorted_list_quicksort = quicksort(list_for_quicksort)
end_time = time.time()
time_quicksort = end_time – start_time
# Measure the time taken by MergeSort
start_time = time.time()
sorted_list_mergesort = mergesort(list_for_mergesort)
end_time = time.time()
time_mergesort = end_time – start_time
# Determine the winner
if time_quicksort < time_mergesort:
print(f”QuickSort won! Time taken: {time_quicksort:.6f} seconds”)
else:
print(f”MergeSort won! Time taken: {time_mergesort:.6f} seconds”)
“`
After running their programs, they compared the execution times. To their surprise, the results were clear. MergeSort finished sorting the list slightly faster than QuickSort.
Taylor grinned, “Seems like theoretical guarantees do pay off sometimes!”
Alex laughed, “You got me! Dinner’s on me. But remember, this was a particularly large list. QuickSort still has its advantages on smaller lists or with certain types of data.”
They both acknowledged that friendly competition and learning from each other were the real winners of the day.