Sorting algorithms are the classic introduction to algorithmic thinking — not because you’ll implement your own sort in production (never do that, use the standard library), but because comparing them teaches how to reason about time and space trade-offs.
def bubble_sort(arr):
# O(n^2) - simple but genuinely impractical past small inputs
n = len(arr)
for i in range(n):
for j in range(n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
def merge_sort(arr):
# O(n log n), stable, but needs O(n) extra space
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left, right = merge_sort(arr[:mid]), merge_sort(arr[mid:])
result, i, j = [], 0, 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
return result + left[i:] + right[j:]
Why Quicksort Usually Wins in Practice
Quicksort’s average case is O(n log n) like merge sort, but it sorts in-place (no extra memory) and has better real-world cache locality — which is exactly why most standard library sort implementations (Python’s Timsort is a hybrid, but many languages’ defaults lean quicksort-derived) favor it despite its worse O(n²) worst case, which good pivot selection makes rare in practice.