Essential Algorithms: Sorting, Searching & Complexity
Big-O is the language engineers use to talk about scale. Whether you're sorting 1,000 transactions or 1 billion log lines at YouTube, the choice between O(n log n) and O(n²) decides if your job finishes in seconds or hours. Every FAANG interview, every system design discussion, starts here, and Python's Timsort (C.A. Hoare meets Tim Peters) is one of the most-studied real-world sort algorithms.
Learning Objectives
After this lesson, you will be able to:
- Explain Big O notation and rank common complexities
- Implement linear search and binary search
- Implement bubble sort and merge sort
- Analyze why algorithm choice matters for performance
- Choose the right algorithm based on data size and constraints
- Implement bubble, insertion, merge, and quicksort from scratch and explain their time/space complexity
- Explain why Python uses Timsort and when to use each sorting algorithm
Prerequisites
Before You Start
#Big O Notation
Big O notation describes how an algorithm's time (or space) grows as the input size grows. It answers: "If I double the input, how much longer does this take?"
#Common Big O Complexities
| Big O | Name | Example | 1,000 items | 1,000,000 items |
|---|---|---|---|---|
| O(1) | Constant | Dictionary lookup | 1 op | 1 op |
| O(log n) | Logarithmic | Binary search | 10 ops | 20 ops |
| O(n) | Linear | Linear search | 1,000 ops | 1,000,000 ops |
| O(n log n) | Linearithmic | Merge sort | 10,000 ops | 20,000,000 ops |
| O(n^2) | Quadratic | Bubble sort | 1,000,000 ops | 1,000,000,000,000 ops |
pythonrunnable cell
import time
def measure_time(func, *args):
"""Measure execution time of a function."""
start = time.time()
result = func(*args)
elapsed = time.time() - start
return result, elapsed
# O(1) -- constant time: dictionary lookup
def dict_lookup(data: dict, key: str):
return data.get(key)
# O(n) -- linear time: search through a list
def linear_search(arr: list, target):
for item in arr:
if item == target:
return True
return False
# O(n^2) -- quadratic time: check all pairs
def has_duplicate_pair(arr: list):
n = len(arr)
for i in range(n):
for j in range(i + 1, n):
if arr[i] == arr[j]:
return True
return False
# Demonstrate scaling
sizes = [1000, 5000, 10000]
for size in sizes:
data = list(range(size))
_, elapsed = measure_time(has_duplicate_pair, data)
print(f"O(n^2) with n={size:>6}: {elapsed:.4f}s")
# Notice: 5x input = ~25x time (quadratic)What Do You Think?
You double the input size. Sorting takes 4x longer. What's the Big O?
How Algorithms Scale — Big O ComplexityInteractive
Loading visualization...
Quick check
What's the time complexity of binary search on a sorted array of n elements?
#Searching Algorithms
#Linear Search: O(n)
Linear search checks every element one by one. Simple but slow for large datasets.
pythonrunnable cell
def linear_search(arr: list, target) -> int:
"""Find target in arr. Return index or -1 if not found.
Time complexity: O(n) -- must check each element in the worst case.
Space complexity: O(1) -- no extra memory needed.
"""
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
numbers = [4, 2, 7, 1, 9, 3, 8, 5]
print(linear_search(numbers, 9)) # 4 (index of 9)
print(linear_search(numbers, 6)) # -1 (not found)Loading visualization...
#Binary Search: O(log n)
Binary search works on sorted data. It cuts the search space in half each step.
pythonrunnable cell
def binary_search(arr: list, target) -> int:
"""Find target in a SORTED array. Return index or -1 if not found.
Time complexity: O(log n) -- halves the search space each step.
Space complexity: O(1) -- uses only two pointers.
"""
left = 0
right = len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1 # target is in the right half
else:
right = mid - 1 # target is in the left half
return -1
sorted_numbers = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
print(binary_search(sorted_numbers, 7)) # 3
print(binary_search(sorted_numbers, 12)) # -1Loading visualization...
#Performance Comparison
pythonreference · read-only
import time
# Create a sorted list of 10 million numbers
data = list(range(10_000_000))
target = 9_999_999 # worst case -- near the end
# Linear search
start = time.time()
linear_search(data, target)
linear_time = time.time() - start
# Binary search
start = time.time()
binary_search(data, target)
binary_time = time.time() - start
print(f"Linear search: {linear_time:.4f}s")
print(f"Binary search: {binary_time:.6f}s")
print(f"Binary is {linear_time / binary_time:.0f}x faster")
# Linear search: ~0.5s
# Binary search: ~0.000005s
# Binary is ~100,000x fasterBinary search on 10 million items takes about 23 comparisons (log2(10,000,000) is ~23). Linear search takes up to 10 million comparisons. That is the power of O(log n).
Quick check
You need to find one item in an unsorted list of 10 million, exactly once. Should you sort it first so you can binary search?
Binary Search — Watch the Range Halve at Every StepInteractive
Loading visualization...
#Sorting Algorithms
#Bubble Sort: O(n^2)
Bubble sort repeatedly swaps adjacent elements that are out of order. Simple to understand but impractical for large datasets.
pythonrunnable cell
def bubble_sort(arr: list) -> list:
"""Sort a list using bubble sort.
Time complexity: O(n^2) -- nested loops comparing every pair.
Space complexity: O(1) -- sorts in place.
"""
arr = arr.copy() # do not modify the original
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] # swap
swapped = True
if not swapped:
break # already sorted -- exit early
return arr
print(bubble_sort([64, 34, 25, 12, 22, 11, 90]))
# [11, 12, 22, 25, 34, 64, 90]#Merge Sort: O(n log n)
pythonrunnable cell
def merge_sort(arr: list) -> list:
"""Sort a list using merge sort.
Time complexity: O(n log n) -- divides in half (log n levels), merges all elements per level (n).
Space complexity: O(n) -- needs temporary arrays for merging.
"""
if len(arr) <= 1:
return arr
# Divide
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
# Merge
return merge(left, right)
def merge(left: list, right: list) -> list:
"""Merge two sorted lists into one sorted list."""
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
# Append any remaining elements
result.extend(left[i:])
result.extend(right[j:])
return result
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
# [3, 9, 10, 27, 38, 43, 82]#Sorting Performance Comparison
pythonreference · read-only
import time
import random
def compare_sorts(n: int) -> None:
"""Compare bubble sort vs merge sort on random data."""
data = [random.randint(0, n * 10) for _ in range(n)]
start = time.time()
bubble_sort(data)
bubble_time = time.time() - start
start = time.time()
merge_sort(data)
merge_time = time.time() - start
start = time.time()
sorted(data) # Python's built-in Timsort (O(n log n))
builtin_time = time.time() - start
print(f"n={n:>6} | Bubble: {bubble_time:.4f}s | Merge: {merge_time:.4f}s | Built-in: {builtin_time:.6f}s")
compare_sorts(1000)
compare_sorts(5000)
compare_sorts(10000)
# n= 1000 | Bubble: 0.0450s | Merge: 0.0020s | Built-in: 0.000070s
# n= 5000 | Bubble: 1.1200s | Merge: 0.0110s | Built-in: 0.000400s
# n= 10000 | Bubble: 4.5000s | Merge: 0.0230s | Built-in: 0.000900s#When to Use Which
| Algorithm | Time | Space | When to use |
|---|---|---|---|
| Bubble Sort | O(n^2) | O(1) | Never in practice (educational only) |
| Merge Sort | O(n log n) | O(n) | When you need guaranteed O(n log n) and stability |
Python sorted() | O(n log n) | O(n) | Always in production — Timsort is highly optimized |
| Binary Search | O(log n) | O(1) | When data is sorted and you need fast lookup |
| Linear Search | O(n) | O(1) | When data is unsorted or very small |
Watch Sorting Algorithms RaceInteractive
Pick an algorithm, hit play, and watch it sort. Compare Bubble Sort's O(n^2) slog against Quick Sort's O(n log n) speed. Pay attention to the comparison and swap counts!
Loading visualization...
What Do You Think?
Bubble sort takes 4.5s on 10,000 items while Python's built-in takes 0.0009s — 5000x faster. Both sort. Where does that gap come from?
#Algorithms in ML Context
pythonrunnable cell
# Binary search is used everywhere in ML:
# 1. Hyperparameter tuning -- binary search for optimal learning rate
def find_best_lr(evaluate_fn, low=1e-5, high=1.0, steps=20):
"""Binary search for the best learning rate."""
for _ in range(steps):
mid = (low + high) / 2
loss_low = evaluate_fn(low + (mid - low) / 3)
loss_high = evaluate_fn(mid + (high - mid) / 3)
if loss_low < loss_high:
high = mid
else:
low = mid
return (low + high) / 2
# 2. K-Nearest Neighbors relies on efficient sorting/searching
def knn_predict(train_data, train_labels, query, k=3):
"""Predict using K-Nearest Neighbors."""
distances = []
for i, point in enumerate(train_data):
dist = sum((a - b) ** 2 for a, b in zip(point, query)) ** 0.5
distances.append((dist, train_labels[i]))
# Sort by distance -- O(n log n)
distances.sort(key=lambda x: x[0])
# Take k nearest
k_nearest = [label for _, label in distances[:k]]
# Return majority vote
from collections import Counter
return Counter(k_nearest).most_common(1)[0][0]
# Example
train_X = [[1, 2], [2, 3], [3, 1], [6, 5], [7, 7], [8, 6]]
train_y = ["A", "A", "A", "B", "B", "B"]
print(knn_predict(train_X, train_y, [5, 5], k=3)) # B
# 3. Python's sorted() is Timsort -- the best general-purpose sort
# Always use it in production instead of implementing your own
data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
print(sorted(data)) # ascending
print(sorted(data, reverse=True)) # descending
print(sorted(data, key=lambda x: -x)) # descending (alt)#Code Playground
pythonplayground.py · Pyodide
Tests · Implement search and sort algorithms, then compare performance!
#Complete Sorting Algorithm Guide
Understanding sorting algorithms builds your algorithm design intuition. Here are all major algorithms, from educational to practical:
#O(n²) Algorithms: Educational but Slow
pythonrunnable cell
# Bubble Sort — repeatedly swap adjacent out-of-order elements
# Time: O(n²) worst/avg, O(n) best (already sorted with flag)
def bubble_sort(arr):
n = len(arr)
for i in range(n):
swapped = False
for j in range(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 # already sorted
return arr
# Selection Sort — find minimum, place at front, repeat
# Time: O(n²) always. Space: O(1)
def 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
# Insertion Sort — build sorted portion one element at a time
# Time: O(n²) worst, O(n) best. Fast for small/nearly-sorted data
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#O(n log n) Algorithms: Production Grade
pythonrunnable cell
# Merge Sort — divide and conquer, stable sort
# Time: O(n log n) always. Space: O(n)
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
# Quick Sort — partition around pivot, in-place
# Time: O(n log n) avg, O(n²) worst (bad pivot choice). Space: O(log n)
def quick_sort(arr, low=0, high=None):
if high is None:
high = len(arr) - 1
if low < high:
pivot_idx = partition(arr, low, high)
quick_sort(arr, low, pivot_idx - 1)
quick_sort(arr, pivot_idx + 1, high)
return arr
def partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1#Python's Built-in: Timsort
Python's
list.sort() and sorted() use Timsort — a hybrid of merge sort and insertion sort:- Finds already-sorted "runs" in the data
- Uses insertion sort for small runs (typically fewer than 64 elements, fast in practice)
- Merges runs using merge sort
- O(n log n) worst case, O(n) best case (already sorted)
- Stable (equal elements maintain original order)
- Adaptive (fast on real-world data which is often partially sorted)
Timsort is designed for real data (file lists, database records, timestamps) which often have sorted "chunks."
Quick check
Timsort is O(n log n) worst case but O(n) on already-sorted input. Merge sort is O(n log n) either way. What does Timsort do that merge sort cannot?
pythonrunnable cell
# Python's built-in sort is almost always the right choice
arr = [3, 1, 4, 1, 5, 9, 2, 6]
arr.sort() # in-place, O(n log n)
new_arr = sorted(arr) # returns new list
# Sort with a key function
students = [("Alice", 92), ("Bob", 78), ("Charlie", 95)]
students.sort(key=lambda s: s[1]) # sort by grade ascending
students.sort(key=lambda s: s[1], reverse=True) # descending
# Sort complex objects
from dataclasses import dataclass
@dataclass(order=True)
class Task:
priority: int
name: str
tasks = [Task(3, "low"), Task(1, "urgent"), Task(2, "normal")]
tasks.sort() # sorts by priority (dataclass order=True uses field order)#Algorithm Comparison Table
| Algorithm | Best | Average | Worst | Space | Stable? | When to use |
|---|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Never (educational only) |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No | Never (educational only) |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Small or nearly-sorted data |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | When stable + guaranteed O(n log n) needed |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No | In-place sort, good cache performance |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | When O(1) extra space required |
| Timsort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | Real-world data (Python's default) |
| Counting Sort | O(n+k) | O(n+k) | O(n+k) | O(k) | Yes | Small integer range (k is value range) |
| Radix Sort | O(nk) | O(nk) | O(nk) | O(n+k) | Yes | Integer keys, fixed width |
Rule of thumb: Always use Python's
sorted() or .sort() in production. Only implement sorting yourself for learning or when you need specific behavior (like an online sort, external sort, or counting sort for integer data).#When to NOT Sort
Sometimes you do not need a full sort:
pythonreference · read-only
import heapq
# Do not sort to find min/max — O(n) is better than O(n log n)
max_val = max(arr) # O(n)
min_val = min(arr) # O(n)
top_3 = heapq.nlargest(3, arr) # O(n log 3) ≈ O(n)
# Do not sort to check if sorted — O(n)
is_sorted = all(arr[i] <= arr[i+1] for i in range(len(arr)-1))
# Do not sort to find a single element — use binary search on already-sorted data
import bisect
idx = bisect.bisect_left(sorted_arr, target) # O(log n)#Key Takeaways
- Big O describes growth rate, not exact speed — O(n^2) means doubling input quadruples the time. O(n log n) means doubling input slightly more than doubles the time. Always think about how your code scales
- Linear search is O(n), binary search is O(log n) — binary search is dramatically faster but requires sorted data. For 10 million items, that is 23 comparisons vs 10 million
- Bubble sort is O(n^2), merge sort is O(n log n) — merge sort divides the problem in half at each level and merges sorted halves. In practice, always use Python's built-in
sorted()which implements Timsort - Algorithm choice has massive real-world impact — the difference between O(n) and O(n^2) on a million items is seconds vs days. In ML, this determines whether training takes minutes or months
- Python's built-in sort is Timsort — a hybrid of merge sort and insertion sort, optimized for real-world data. Use
sorted()or.sort()in production, not hand-written sorts
Quick Check1 / 5
What does O(n^2) mean in Big O notation?