Sorting Algorithms — Bubble, Insertion, Selection, and Beyond
sorting-algorithms not found in registry.Why Sorting Matters
Sorting is one of the most studied problems in computer science. Search engines rank results, databases return ordered queries, spreadsheets sort columns — and underneath it all is a sorting algorithm.
Understanding sorts teaches you about time complexity trade-offs, divide-and-conquer, and stability. Plus, sorting questions are interview favourites.
Bubble Sort
Bubble sort repeatedly walks through the list, compares adjacent elements, and swaps them if they are in the wrong order. Larger elements "bubble up" to the end. After each pass, the largest unsorted element is in its correct position.
Simple to understand, terrible in practice — O(n²) for almost all inputs.
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
data = [38, 27, 43, 3, 9, 82, 10]
print("Before:", data)
print("After:", bubble_sort(data))Insertion Sort
Insertion sort builds the sorted array one element at a time. It picks each element and inserts it into its correct position among the already-sorted elements — like sorting a hand of playing cards.
O(n²) worst case, but O(n) on nearly-sorted data. Great for small or nearly-sorted inputs.
def 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
data = [38, 27, 43, 3, 9, 82, 10]
print("Before:", data)
print("After:", insertion_sort(data))Merge Sort
Merge sort is a divide-and-conquer algorithm. Split the array in half, recursively sort each half, then merge the two sorted halves. Guaranteed O(n log n) regardless of input order.
The trade-off: it needs O(n) extra space for the merge step.
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
data = [38, 27, 43, 3, 9, 82, 10]
print("Before:", data)
print("After:", merge_sort(data))| Algorithm | Best | Average | Worst | Space | Stable? |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
Key Takeaways
- Bubble and Selection sort are O(n²) — fine for tiny inputs, terrible for anything else.
- Insertion sort is O(n²) worst case but O(n) on nearly sorted data. Python uses it internally for small arrays.
- Merge sort guarantees O(n log n) but needs O(n) extra space.
- Quick sort is O(n log n) on average with O(log n) space, but O(n²) worst case with bad pivot choices.
- Python’s built-in
sorted()uses Timsort — a hybrid of merge sort and insertion sort.