Sorting and Searching Algorithms

TL;DR

You'll learn how the major sorting algorithms (bubble, merge, quick, Timsort) actually work and why their time complexities differ. You'll understand binary search and why it needs sorted data. By the end, you'll know which algorithm to reach for given data size, memory limits, and whether the data's already partially ordered.

1. The Mental Model

Sorting is just organized swapping or merging — every algorithm is a different strategy for deciding which elements to compare and move. Searching trades time for structure: if you pay the cost to sort first, every future search gets cheap. The real skill here isn't memorizing code, it's matching the shape of your data (size, randomness, memory budget) to the right algorithm. Sorting is an investment; searching is where you cash in the interest.

2. The Core Material

2.1 Comparison Sorts: The O(n²) Family and Why They're Taught

Photo by cottonbro studio on Pexels

Bubble sort, insertion sort, and selection sort all run in O(n²) time, but they teach you the core moves every sorting algorithm uses: compare, swap, track a boundary between "sorted" and "unsorted."

Insertion sort is the one worth actually using sometimes — it's O(n) on nearly-sorted data because the inner loop barely runs.

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

Each outer iteration takes the next element and slides it left until it finds its spot. On random data, that's O(n²) comparisons on average. On data that's already 95% sorted, the while loop almost never triggers, so it's close to O(n). This is why Python's real-world sort (Timsort) leans on insertion sort for small chunks.

2.2 Divide-and-Conquer: Merge Sort and Quicksort

These are the two sorts that actually matter in interviews and in understanding how fast sorting can be.

Merge sort splits the array in half recursively until pieces have 1 element, then merges pairs back together in sorted order.

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

Why O(n log n)? You split the array log₂(n) times (each level halves the size), and merging all pieces at any one level costs O(n) total comparisons. log₂(n) levels × O(n) work per level = O(n log n). This bound is always hit — best, worst, and average case — because merge sort doesn't care about input order. The cost is O(n) extra space for the merge buffers.

Quicksort picks a pivot, partitions everything smaller to its left and larger to its right, then recurses on each side.

def quicksort(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    if low < high:
        pivot_idx = partition(arr, low, high)
        quicksort(arr, low, pivot_idx - 1)
        quicksort(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

Quicksort's average case is O(n log n), same as merge sort, but with better constants in practice because it sorts in place (O(log n) stack space, not O(n) extra arrays) and has better cache behavior. The catch: worst case is O(n²) — if your pivot choice is consistently bad (e.g., always picking the last element on already-sorted data), each partition only shrinks the problem by 1 instead of roughly halving it. Real-world quicksorts use random pivots or "median of three" to make the worst case astronomically unlikely.

flowchart TD
    A["Unsorted array [5,2,8,1,9,3]"] --> B{"Pick pivot = 3"}
    B --> C["Partition: smaller left, larger right"]
    C --> D["[2,1] | 3 | [5,8,9]"]
    D --> E["Recurse left: [2,1]"]
    D --> F["Recurse right: [5,8,9]"]
    E --> G["Sorted: [1,2]"]
    F --> H["Sorted: [5,8,9]"]
    G --> I["Combine: [1,2,3,5,8,9]"]
    H --> I

2.3 Binary Search and Why Order Matters

Photo by Markus Winkler on Pexels

Linear search checks every element: O(n). Binary search exploits sorted order to eliminate half the remaining candidates on each comparison, giving O(log n).

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

Why O(log n)? Each iteration halves the search space. Starting with n elements, after k iterations you have n / 2^k elements left. The search ends when that's ≤ 1, so n / 2^k = 1 → 2^k = n → k = log₂(n). For n = 1,000,000, that's only about 20 comparisons versus up to 1,000,000 for linear search. This is the reason sorting is worth doing upfront if you'll search the same dataset many times — sort once (O(n log n)), then search repeatedly for O(log n) each time, instead of paying O(n) per search forever.

flowchart TD
    A["Array of 16 sorted items, search for x"] --> B{"Check middle: 8 items left"}
    B --> C{"Check middle: 4 items left"}
    C --> D{"Check middle: 2 items left"}
    D --> E{"Check middle: 1 item left"}
    E --> F["Found or not found in 4 steps instead of 16"]

2.4 Timsort: What Python Actually Runs

Photo by Christina Morillo on Pexels

sorted() and list.sort() in Python use Timsort, a hybrid of merge sort and insertion sort. It detects existing "runs" (already-sorted subsequences) in your data, sorts small runs with insertion sort, then merges runs using merge sort logic. This gives O(n log n) worst case but O(n) best case on data with existing order — which is extremely common in real datasets (e.g., log files, mostly-sorted updates). This is why you almost never write your own sort in production Python; the built-in is already near-optimal and handles edge cases (stability, adaptivity) you'd get wrong by hand.

3. Worked Example

Say you have 10,000 student records and need to find all students with a specific ID, repeatedly, across 500 queries.

Approach A — no sorting, linear search each time:
500 queries × 10,000 comparisons = 5,000,000 comparisons.

Approach B — sort once, then binary search:
Sort cost: 10,000 × log₂(10,000) ≈ 10,000 × 13.3 ≈ 133,000 comparisons.
500 queries × log₂(10,000) ≈ 500 × 13.3 ≈ 6,650 comparisons.
Total: ≈ 139,650 comparisons.

That's roughly 36x fewer comparisons. Let's verify this in code:

import random

records = [(i, f"name{i}") for i in range(10000)]
random.shuffle(records)

# Sort once by ID
records.sort(key=lambda r: r[0])

def binary_search_records(records, target_id):
    low, high = 0, len(records) - 1
    while low <= high:
        mid = (low + high) // 2
        if records[mid][0] == target_id:
            return records[mid]
        elif records[mid][0] < target_id:
            low = mid + 1
        else:
            high = mid - 1
    return None

result = binary_search_records(records, 4321)
print(result)  # (4321, 'name4321')

Once sorted, every lookup is O(log n) ≈ 13 comparisons instead of scanning up to 10,000 entries. If you only needed to search once, sorting first wouldn't be worth it — the breakeven point is roughly when the number of queries exceeds log(n), which almost always favors sorting when you query more than a handful of times.

4. Production Pitfalls & Best Practices

4.1 Real-World Best Practices

• Use the built-in sort. Python's sorted()/.sort() (Timsort) beats almost any hand-rolled sort in both speed and correctness. Reserve custom sorts for interviews or when you need a specific algorithm's guarantees (e.g., in-place with O(1) space).
• Use key= instead of custom comparators. sorted(data, key=lambda x: x.age) is faster and clearer than writing a cmp function — Python decorates each item once instead of recomputing on every comparison.
• Check stability when sorting multi-field data. Timsort is stable (equal elements keep their relative order), so you can sort by secondary key first, then primary key, and get correct multi-level sorting.
• Use bisect module for binary search in production, not hand-written loops — bisect.bisect_left and bisect.insort are C-optimized and battle-tested.
• Randomize pivot choice in quicksort if you ever implement it yourself, to avoid worst-case O(n²) on adversarial or already-sorted input.
• Profile before optimizing. For n < ~1000, the O(n²) vs O(n log n) difference rarely matters in wall-clock time; constant factors and Python's interpreter overhead dominate.

4.2 Common Bugs & Anti-Patterns

Bug 1: Binary search on unsorted data (silently wrong results).

# BAD
arr = [5, 1, 9, 3]
binary_search(arr, 9)  # may return -1 even though 9 is present

# FIXED
arr = sorted([5, 1, 9, 3])
binary_search(arr, 9)  # correctly finds it

Bug 2: Off-by-one in binary search bounds causing infinite loop.

# BAD — mid calculation can repeat same index forever
while low < high:
    mid = (low + high) // 2
    if arr[mid] < target:
        low = mid        # bug: should be mid + 1
    else:
        high = mid

# FIXED
while low <= high:
    mid = (low + high) // 2
    if arr[mid] < target:
        low = mid + 1
    else:
        high = mid - 1

Bug 3: Using a mutable default or sorting in place when you meant to copy.

# BAD — mutates caller's list unexpectedly
def get_sorted(records):
    records.sort()
    return records

# FIXED — returns a new sorted list, leaves original untouched
def get_sorted(records):
    return sorted(records)

Bug 4: Naive quicksort pivot on sorted/reverse-sorted input causing O(n²) blowup.

# BAD — always picks last element as pivot
def partition(arr, low, high):
    pivot = arr[high]  # worst case on sorted input

# FIXED — randomize to avoid pathological input
import random
def partition(arr, low, high):
    rand_idx = random.randint(low, high)
    arr[rand_idx], arr[high] = arr[high], arr[rand_idx]
    pivot = arr[high]

4.3 When to Use What (Decision Matrix)

5. Now Try It

Write a function closest_pair(arr, target) that, given a sorted list of integers and a target value, returns the two adjacent elements in the array that target would sit between (using binary search logic, not a linear scan). For example, closest_pair([1, 4, 7, 10, 15], 9) should return (7, 10). Test it with at least 3 inputs, including a target smaller than everything and larger than everything (handle those edge cases explicitly, e.g., return (None, arr[0]) or (arr[-1], None)).

Success looks like: your function runs in O(log n) time (uses binary search, not a for loop over the whole array) and correctly handles values at both ends of the array.