def bubble_sort(arr):
n = len(arr)
for i in range(n):
swapped = False
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped:
break
return arr
# O(n²) time, O(1) space, stabledef selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
# O(n²) time, O(1) space, NOT stabledef insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
# O(n²) time, O(1) space, stable, fast for nearly sorted!def merge_sort(arr):
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 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
# O(n log n) time, O(n) space, stabledef quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
# O(n log n) avg, O(n²) worst, O(n) space (not in-place here)def heap_sort(arr):
import heapq
heapq.heapify(arr)
return [heapq.heappop(arr) for _ in range(len(arr))]
# O(n log n) time, O(1) space, NOT stabledef counting_sort(arr):
if not arr: return []
min_val, max_val = min(arr), max(arr)
count = [0] * (max_val - min_val + 1)
for x in arr:
count[x - min_val] += 1
result = []
for i, c in enumerate(count):
result.extend([i + min_val] * c)
return result
# O(n + k) time, O(k) space, where k = range of values# Timsort = Merge Sort + Insertion Sort
# O(n log n) worst case
# O(n) best case (already sorted!)
# Stable
# In-place (.sort()) or new list (sorted())
arr = [5, 2, 8, 1, 9, 3]
print(sorted(arr)) # [1, 2, 3, 5, 8, 9]
print(arr) # [5, 2, 8, 1, 9, 3] (unchanged)
arr.sort()
print(arr) # [1, 2, 3, 5, 8, 9] (modified)
# Custom key
students = [('Alice', 85), ('Bob', 92), ('Charlie', 85)]
print(sorted(students, key=lambda x: (-x[1], x[0])))
# [('Bob', 92), ('Alice', 85), ('Charlie', 85)]Implement: `bubble_sort`, `selection_sort`, `insertion_sort`, `merge_sort` (with helper `merge`), `quick_sort`, and `counting_sort`. All should return a NEW sorted list (don't modify input, make copies first). Write a `benchmark_sorts()` function that times each sort on a list of 1000 random integers using `time.perf_counter()`. Print results sorted by speed.