Searching & Sorting

Searching and sorting are where Big-O becomes visceral — the gap between O(n) and O(log n), or between O(n²) and O(n log n), is not just numbers on paper. It is the difference between a program that answers instantly and one that hangs for seconds. This lesson is also a judgment exercise: an AI can generate five different sorting functions in seconds, but only you can tell which one is correct, which one is fast enough, and which one is stable — a property that silently breaks production systems when ignored.

Linear vs binary search

Linear search walks through items one by one from the start until it finds the target (or runs out). It works on any data with no prior ordering required, but in the worst case it must inspect every element, so it is O(n).

Binary search is far faster at O(log n), but it comes with one hard condition: the data must already be sorted.

The core idea is halving: look at the middle value of the range.

If middle == target → found it.
If middle < target → the target must be in the right half; discard the left.
If middle > target → the target must be in the left half; discard the right.

Every step throws away half of what remains. A list of 1,000,000 items needs only about 20 steps to find anything (because log₂(1,000,000) ≈ 20), versus up to a million checks for linear search.

Binary search, carefully

Binary search is alarmingly easy to get wrong. The classic pitfalls are the bounds of lo, mid, hi and the off-by-one errors that cause infinite loops or skip the value you needed. Here is a correct version:

def binary_search(arr, target):
    lo = 0
    hi = len(arr) - 1        # hi indexes the LAST still-possible element

    while lo <= hi:          # must be <= not <, to check a 1-element range
        mid = (lo + hi) // 2 # floor division gives the middle index
        if arr[mid] == target:
            return mid       # found; return the index
        elif arr[mid] < target:
            lo = mid + 1     # discard the left half (+1 avoids hanging)
        else:
            hi = mid - 1     # discard the right half (-1 avoids hanging)

    return -1                # not found

Watch out for:

hi = len(arr) - 1, not len(arr) — hi is the index of the last element still under consideration.
while lo <= hi must use <=, not <, or a range that has shrunk to a single element never gets checked.
lo = mid + 1 and hi = mid - 1 must always include the +1/-1. If you write lo = mid or hi = mid, then when the range narrows to 2 elements mid stops moving → infinite loop.

Bug-avoidance tip: use mid = lo + (hi - lo) // 2 instead of (lo + hi) // 2 in languages with bounded integers (Java/C++) to avoid integer overflow — unnecessary in Python, where ints grow without limit.

Sorting overview

Most of the sorting algorithms you study are comparison sorts: they decide order by comparing pairs of values to see which comes first. The rest of this lesson splits them into two families: the simple O(n²) sorts you should understand deeply but rarely write in production, and the O(n log n) sorts that power every real standard library.

Stability — a sorting algorithm is stable if equal values keep their original relative order after sorting.

Why care? Suppose you first sort a list of employees by name, then sort again by department. If the algorithm is stable, people in the same department remain ordered by name — letting you layer multiple sorts. If it is unstable, the earlier name ordering is scrambled.

The O(n²) sorts: bubble, selection, insertion

These three are the “obvious” sorts — the kind you might invent yourself before learning anything cleverer. All three compare adjacent or nearby elements and require, in the worst case, roughly n²/2 comparisons. They differ in how they move elements and, crucially, in whether they preserve stability.

Bubble sort

Repeatedly scan the array, swapping any adjacent pair that is out of order. Each full pass “bubbles” the largest remaining value to its correct position at the end.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):     # last i elements are already sorted
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:                # early exit: nothing moved this pass
            break
    return arr

Because a swap only happens when arr[j] > arr[j+1] (strictly greater), two equal elements are never swapped past each other — bubble sort is stable.

Trace on [5, 3, 8, 4, 2]:

Pass	Comparisons (swap?)	Array after pass	Swaps
1	(5,3)✓ (5,8)✗ (8,4)✓ (8,2)✓	`[3, 5, 4, 2, 8]`	3
2	(3,5)✗ (5,4)✓ (5,2)✓	`[3, 4, 2, 5, 8]`	2
3	(3,4)✗ (4,2)✓	`[3, 2, 4, 5, 8]`	1
4	(3,2)✓	`[2, 3, 4, 5, 8]`	1

Fully sorted after 4 passes and 7 swaps total. A final pass with zero swaps confirms it is done — that “no swaps” check is what makes bubble sort’s best case O(n) on already-sorted input.

Selection sort

Find the minimum of the unsorted remainder, then swap it into the front position. Repeat for the rest of the array.

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        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]   # single swap per pass
    return arr

Selection sort always scans the entire remaining unsorted region to find the minimum, regardless of how sorted the input already is — so unlike bubble sort, it has no early exit and is O(n²) even in the best case.

Worse, the single swap at the end of each pass can leapfrog an element past an equal one, so selection sort is not stable. Example, sorting by the number and keeping the letter as a tag:

[(5,A), (3,B), (5,C), (1,D)] → the minimum is (1,D) at index 3, swapped with index 0: [(1,D), (3,B), (5,C), (5,A)] — notice (5,C) now sits before (5,A), even though A came before C in the original array. The relative order of equal elements got reversed.

Insertion sort

Build a sorted prefix one element at a time: take the next element and shift it leftward past every larger element already in the sorted prefix, then drop it in place.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:   # strictly greater keeps it stable
            arr[j + 1] = arr[j]          # shift larger element right
            j -= 1
        arr[j + 1] = key                 # drop key into the gap
    return arr

The while condition uses arr[j] > key (strictly greater), so an equal element is never shifted past key — insertion sort is stable. It is also the fastest of the three on nearly sorted data, because each element only shifts as far as it needs to — its best case is O(n).

The O(n log n) sorts: divide and conquer

Both algorithms below beat O(n²) using the same trick: divide and conquer — split the problem into smaller pieces, solve each recursively, then combine. The recursion depth is log n (halving each time), and each level of recursion does O(n) total work, giving O(n log n).

Merge sort — divide, then combine

Split the list in half recursively until only single elements remain (trivially “sorted”), then merge sorted halves back together by repeatedly taking the smaller front element.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])       # divide
    right = merge_sort(arr[mid:])      # divide
    return merge(left, right)          # combine

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:        # <= (not <) keeps left-side ties first: STABLE
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    result.extend(left[i:])            # append any leftovers
    result.extend(right[j:])
    return result

Splitting [8, 3, 7, 4, 2, 6, 1, 5] in half repeatedly:

[8,3,7,4,2,6,1,5]
[8,3,7,4]        [2,6,1,5]
[8,3]  [7,4]     [2,6]  [1,5]
[8][3] [7][4]    [2][6] [1][5]     <- base case: single elements
[3,8]  [4,7]     [2,6]  [1,5]      <- merge pairs
   [3,4,7,8]        [1,2,5,6]      <- merge quads
      [1,2,3,4,5,6,7,8]            <- final merge

Merge sort is O(n log n) in the best, average, and worst case — no bad input can slow it down — and it is stable because merge picks from the left side on ties. The cost: the result lists need O(n) extra memory (it is not in-place).

Quicksort — partition, then recurse

Pick a pivot, rearrange the array so everything <= the pivot comes before it and everything greater comes after (partitioning), then recursively sort each side. Unlike merge sort, the combine step is free — once both sides are sorted, the whole array is sorted.

def quicksort(arr, lo=0, hi=None):
    if hi is None:
        hi = len(arr) - 1
    if lo < hi:
        p = partition(arr, lo, hi)
        quicksort(arr, lo, p - 1)      # recurse left of the pivot
        quicksort(arr, p + 1, hi)      # recurse right of the pivot

def partition(arr, lo, hi):
    pivot = arr[hi]                    # last element as pivot (simple, but riskiest choice)
    i = lo - 1
    for j in range(lo, hi):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[hi] = arr[hi], arr[i + 1]
    return i + 1                       # pivot's final resting index

Quicksort averages O(n log n) and, because it works in-place with small constants, is usually faster in practice than merge sort. But its worst case is O(n²): if the pivot is always the smallest or largest remaining element, partitioning splits n items into groups of n-1 and 0 — no better than doing nothing. A sorted array with a “last element” pivot is exactly this worst case. The swaps inside partition also reorder equal elements arbitrarily, so quicksort is generally not stable. (Randomizing the pivot, or picking the median of three candidates, makes the O(n²) worst case astronomically unlikely — but never impossible by construction alone.)

The O(n log n) lower bound — why you can’t do better

It can be proven, not just observed, that any algorithm that sorts purely by comparing pairs of elements needs Ω(n log n) comparisons in the worst case. The intuition is a decision tree:

Any comparison-based sort, run on n distinct elements, must be able to produce any of the n! possible orderings as output.
Each comparison has only two outcomes (< or >), so think of the algorithm as a binary tree of comparisons: each leaf corresponds to one specific final ordering.
To distinguish n! different orderings, the tree needs at least n! leaves, so its depth — the worst-case number of comparisons — must be at least log₂(n!).
By Stirling’s approximation, log₂(n!) = Ω(n log n).

Small example: for n = 3 elements, there are 3! = 6 possible orderings. A binary decision tree needs ⌈log₂ 6⌉ = 3 levels to have 6 distinguishable leaves — so any correct comparison sort needs up to 3 comparisons to sort 3 elements, no matter how cleverly it’s written. This is exactly why merge sort and quicksort, at O(n log n), are considered optimal among comparison sorts — you cannot invent a comparison-based sort that beats them asymptotically. (Non-comparison sorts like counting sort or radix sort can beat O(n log n) — but only because they exploit extra structure, like a bounded range of integer keys, instead of comparing values.)

Why stability matters in practice

Stability sounds academic until you need to sort by more than one key. Suppose you have a list of orders and want them sorted by region, and within each region, by order_date:

orders = [
    {"region": "West", "date": "2024-03-01"},
    {"region": "East", "date": "2024-01-15"},
    {"region": "West", "date": "2024-01-20"},
    {"region": "East", "date": "2024-02-10"},
]

# Sort by the secondary key FIRST, then the primary key.
# A stable sort keeps the date ordering intact within each region.
orders.sort(key=lambda o: o["date"])     # 1st sort: by date
orders.sort(key=lambda o: o["region"])   # 2nd sort: by region (stable! keeps date order)

This “sort twice” trick only works because Python’s sort() is guaranteed stable. If you used an unstable sort (like a naive quicksort or selection sort) for the second pass, the date ordering within each region could come out scrambled — a subtle bug that only shows up with duplicate keys, which is exactly the case real data hits constantly (many orders share a region).

Timsort — what `sorted()` actually runs

Python’s sorted() and list.sort() (and Java’s Arrays.sort() for objects) don’t use a textbook merge sort or quicksort — they use Timsort, a hybrid designed by Tim Peters specifically to exploit patterns in real-world data:

It scans for existing runs — contiguous ascending or descending stretches already present in the data (real-world data is rarely fully random; it often has partial order) — and reverses descending runs in place.
Short runs (below a threshold, typically 32–64 elements) are extended and sorted with insertion sort — which is fast on small/nearly-sorted inputs.
Longer runs are combined using a careful merge sort–style merge.
The result: O(n) in the best case (e.g., the input is already sorted or reverse-sorted), O(n log n) in the worst and average case, and — crucially — guaranteed stable, which is why the “sort twice” pattern above is safe to rely on.

Practical takeaway: never hand-write a bubble/selection/insertion sort for production code sorting real data. Use your language’s built-in sort (Timsort in Python/Java, Introsort in C++/std::sort) — it is both asymptotically optimal and battle-tested against edge cases you haven’t thought of.

Complexity

Algorithm	Best	Average	Worst	Space	Stable?
Linear search	`O(1)`	`O(n)`	`O(n)`	`O(1)`	—
Binary search	`O(1)`	`O(log n)`	`O(log n)`	`O(1)`	—
Bubble sort	`O(n)`	`O(n²)`	`O(n²)`	`O(1)`	Yes
Selection sort	`O(n²)`	`O(n²)`	`O(n²)`	`O(1)`	No
Insertion sort	`O(n)`	`O(n²)`	`O(n²)`	`O(1)`	Yes
Merge sort	`O(n log n)`	`O(n log n)`	`O(n log n)`	`O(n)`	Yes
Quicksort	`O(n log n)`	`O(n log n)`	`O(n²)`	`O(log n)`	No
Timsort (`sorted()`)	`O(n)`	`O(n log n)`	`O(n log n)`	`O(n)`	Yes

Binary search’s best case is O(1) when the target is the very first middle element. Selection sort’s best case is still O(n²) — it always scans the whole remainder to find the minimum, unlike bubble/insertion sort, which can exit early on sorted input.

Real-world problem

Imagine a membership app with 50 million users, stored sorted by user_id in an index file. When someone logs in, we must find their user_id.

With a linear scan, the worst case reads 50 million rows per login — unusably slow when many people log in at once.

With binary search on the sorted data, it takes only about log₂(50,000,000) ≈ 26 steps — millions of times faster.

When does sorting first pay off? Sorting once costs O(n log n), but if you then search repeatedly (k times), the total is O(n log n + k log n), far cheaper than linear search’s O(k·n) when k is large. But if you search only once and then discard the data, a single linear scan O(n) may beat paying to sort the whole pile.

Exercises

1. Hand-trace binary search For the array [1, 3, 5, 7, 9, 11, 13, 15, 17, 19], search for target = 13. Write the values of lo, mid, hi at each iteration until it is found.

Answer

Iter	lo	hi	mid	arr[mid]	Action
1	0	9	4	9	9 < 13 → `lo = 5`
2	5	9	7	15	15 > 13 → `hi = 6`
3	5	6	5	11	11 < 13 → `lo = 6`
4	6	6	6	13	Found! return index 6

Just 4 iterations, versus a linear scan that would inspect up to the 7th element.

2. Find first and last occurrence If the array can contain duplicates, e.g. [2, 4, 4, 4, 6, 8], and you want the first index of value 4, how do you adapt binary search?

Answer

When you hit arr[mid] == target, do not return immediately. Instead “remember the index and keep going left” to find any earlier match:

def first_occurrence(arr, target):
    lo, hi = 0, len(arr) - 1
    ans = -1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            ans = mid        # remember it, then keep searching left
            hi = mid - 1
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return ans

For the last occurrence, do the opposite: on a match, set lo = mid + 1 to keep going right.

3. Why sorted is required Explain why binary search cannot be used on unsorted data. Give an example.

Answer

Binary search decides whether to go left or right using the rule “if the middle value is less than the target, the answer must be to the right.” That rule only holds when the data is sorted.

Example: in [9, 1, 5, 3, 7] searching for 7, the middle is 5. Since 5 < 7, we discard the left and look in the right half [3, 7] — we happen to find it. But searching for 1: the middle 5 > 1, so we discard the right and go to the left half [9], then wrongly conclude “no 1” even though 1 is in the list. Halving is only reliable on sorted data.

4. Spot the off-by-one What is wrong with this code?

def search(arr, target):
    lo, hi = 0, len(arr)        # (a)
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid            # (b)
        else:
            hi = mid
    return -1

Answer

Line (b) is wrong: lo = mid means lo stops moving when the range narrows to 2 elements (because mid equals lo) → infinite loop. It must be lo = mid + 1.

(Note: the half-open style hi = len(arr) paired with while lo < hi and hi = mid can be correct, as long as the lo side always uses mid + 1.)

5. Count binary search steps An array has 1,000,000 elements. How many steps does binary search take in the worst case?

Answer

About ⌈log₂(1,000,000)⌉ = 20 steps, because each step halves the data: 2²⁰ = 1,048,576 > 1,000,000. Compare with linear search, which may inspect all 1,000,000 elements.

6. Trace bubble sort Trace bubble sort on [5, 3, 8, 4, 2]. For each pass, list the comparisons, which ones swap, and the resulting array. How many total swaps happen?

Answer

Pass	Comparisons (swap?)	Array after pass
1	(5,3)✓ (5,8)✗ (8,4)✓ (8,2)✓	`[3, 5, 4, 2, 8]`
2	(3,5)✗ (5,4)✓ (5,2)✓	`[3, 4, 2, 5, 8]`
3	(3,4)✗ (4,2)✓	`[3, 2, 4, 5, 8]`
4	(3,2)✓	`[2, 3, 4, 5, 8]`

Total swaps: 3 + 2 + 1 + 1 = 7 swaps, over 4 passes. A 5th pass would do zero swaps, confirming it’s done.

7. Selection sort breaks stability Sort [(5,'A'), (3,'B'), (5,'C'), (1,'D')] by the numeric key using selection sort, tracking the swaps. Is the final order of the two 5s the same as their original relative order?

Answer

Pass 1: minimum of the whole array is (1,'D') at index 3. Swap with index 0 → [(1,'D'), (3,'B'), (5,'C'), (5,'A')]

Pass 2: minimum of [(3,'B'), (5,'C'), (5,'A')] is (3,'B'), already in place — no swap.

Pass 3: minimum of [(5,'C'), (5,'A')] is (5,'C') (leftmost on ties), already in place — no swap.

Final: [(1,'D'), (3,'B'), (5,'C'), (5,'A')]. Originally A came before C; now C comes before A. Order reversed → selection sort is not stable.

8. Insertion sort’s best case Trace insertion sort on the nearly-sorted array [1, 2, 4, 3, 5]. Count how many element shifts happen in total, and explain why this is close to insertion sort’s O(n) best case rather than its O(n²) worst case.

Answer

i=1, key=2: compare with 1 (not greater) → 0 shifts.
i=2, key=4: compare with 2 (not greater) → 0 shifts.
i=3, key=3: compare with 4 (greater, shift) → 1 shift, then compare with 2 (not greater) → stop, insert 3.
i=4, key=5: compare with 4 (not greater) → 0 shifts.

Total: 1 shift. Because the array is already almost sorted, most elements only need a single comparison to confirm they’re in place — insertion sort’s inner while loop barely runs. On a reverse-sorted array, every element would shift all the way to the front, giving the full O(n²) worst case.

9. Quicksort’s worst case The quicksort/partition code above always picks arr[hi] (the last element) as the pivot. What happens if you run it on the already-sorted array [1, 2, 3, 4, 5]? What is the time complexity, and why?

Answer

On a sorted array, arr[hi] is always the largest remaining element, so every partition puts all other elements on the “less than” side and none on the “greater than” side — the split is n-1 and 0 every time instead of roughly n/2 and n/2. That means the recursion doesn’t halve the problem; it only shrinks it by one element per call, giving n levels of recursion instead of log n, each doing O(n) work → O(n²) total. The fix in practice: choose the pivot randomly, or as the median of the first/middle/last elements, so an already-sorted (or adversarially crafted) input can’t reliably trigger the worst case.

10. Predict the output: stability in a two-pass sort

students = [
    {"name": "Anan", "grade": "B"},
    {"name": "Beau", "grade": "A"},
    {"name": "Cham", "grade": "B"},
    {"name": "Dara", "grade": "A"},
]
students.sort(key=lambda s: s["name"])
students.sort(key=lambda s: s["grade"])
print([s["name"] for s in students])

What does this print, and would the answer change if sort() were not stable?

Answer

Prints ['Beau', 'Dara', 'Anan', 'Cham'].

First sort by name gives [Anan, Beau, Cham, Dara]. The second sort, by grade, groups the As (Beau, Dara) before the Bs (Anan, Cham) — and because Python’s sort() is stable, each group keeps its existing alphabetical order from the first sort. If sort() were unstable, the order within the A group and within the B group could come out in any order (e.g. [Dara, Beau, Cham, Anan]) — the alphabetical-within-grade guarantee would be lost.

AI Code Critique

You ask an AI to write binary search, and it returns this code with the assurance: “Tested and working correctly.”

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid          # <-- look at this line
        else:
            hi = mid          # <-- and this one
    return -1

Task: run binary_search([1, 2, 3], 2) — it will hang forever. Find the bug and fix it.

Answer

The bug is lo = mid and hi = mid with no +1/-1, so the range never shrinks once it holds 2 elements.

Trace binary_search([1, 2, 3], 0): start lo=0, hi=2, mid=1, arr[1]=2 > 0 → hi = 1; next lo=0, hi=1, mid=0, arr[0]=1 > 0 → hi = 0; now lo=0, hi=0, mid=0, arr[0]=1 > 0 → hi = 0 unchanged → loops forever.

Fix it by always moving the bound past mid:

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

Lesson: AI code that “looks correct” can hide off-by-one bugs. Always test with edge cases (such as a value that is not in the list).

Second prompt: “Write a stable sorting function.” The AI returns selection sort and confidently labels it stable.

def stable_sort(arr, key=lambda x: x):
    # AI's comment: "Selection sort — simple and stable."
    n = len(arr)
    for i in range(n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if key(arr[j]) < key(arr[min_idx]):
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

Answer

Selection sort is not stable — see Exercise 7 above for a concrete counterexample where two equal keys get reordered by the final swap in each pass. The AI’s comment is simply wrong; “simple” does not imply “stable,” and the two properties are unrelated. If you actually need a stable sort, either use the built-in sorted()/list.sort() (Timsort, guaranteed stable) or implement merge sort with <= in the merge step. The lesson: always verify a claimed property (stable, in-place, O(n log n)) against the actual algorithm’s mechanics — don’t trust a comment or docstring at face value, especially one an AI wrote about its own code.

🎮 Game Dev: Searching & Sorting

Every frame, a 2D renderer has to decide what order to draw overlapping sprites in — the classic “painter’s algorithm” draws far things first and near things on top, which is nothing more than sorting sprites by depth (y, or a dedicated z-index) before drawing them. Sprites only nudge a pixel or two between frames, so last frame’s order is already nearly sorted — exactly the case insertion sort is built for. And once you have a sorted list — of spawn times, of high scores — binary search turns “find the next event” into an O(log n) lookup instead of an O(n) scan.

Depth-sorting sprites: the painter’s algorithm

class Sprite:
    def __init__(self, name, y, spawn_order):
        self.name = name
        self.y = y                      # depth key: larger y = closer to the camera
        self.spawn_order = spawn_order  # tiebreak: which sprite was created first

# naive first draft: sort by y and hope for the best
def naive_depth_sort(sprites):
    return sorted(sprites, key=lambda s: s.y)

This looks fine — until two sprites share the same y (a torch and a floor decal on the same tile). Python’s sorted() is stable (Timsort), so within one frame tied sprites keep their input-list order. But if sprites gets rebuilt between frames (an enemy dies and is removed, a list gets filtered), the tied pair’s input order can change too — so the tie silently flips draw order, and one decal flickers on top of the other for a frame even though neither one moved. The scaled fix is an explicit tiebreak, so equal-depth sprites always resolve the same way regardless of incidental list order:

def stable_depth_sort(sprites):
    # explicit tiebreak: same y -> whichever sprite existed first draws first
    return sorted(sprites, key=lambda s: (s.y, s.spawn_order))

Because sprites move only a little per frame, the list sorted last frame is already almost sorted this frame — just a few elements need to shift. That is exactly the input insertion sort is fastest on:

def insertion_depth_sort(sprites):
    for i in range(1, len(sprites)):
        current = sprites[i]
        key = (current.y, current.spawn_order)
        j = i - 1
        while j >= 0 and (sprites[j].y, sprites[j].spawn_order) > key:
            sprites[j + 1] = sprites[j]
            j -= 1
        sprites[j + 1] = current
    return sprites

On a nearly-sorted frame this runs close to insertion sort’s O(n) best case — far cheaper than re-sorting from scratch with a general-purpose O(n log n) sort once the sprite count gets large.

y=70 B

y=100 (drawn last, nearest) C

Figure: sprites A (y=40), B (y=70), C (y=100) drawn back-to-front in ascending-y order — each later sprite overlaps the earlier ones, exactly like a painter laying down paint.

Binary search on a sorted spawn timeline

A wave-based game keeps its spawn events as a list sorted by time, e.g. [2, 6, 6, 12, 18, 25, 30, 40]. Every frame you need “what’s the next spawn after now?” — scanning from the start every frame is wasted work once the timeline gets long. Binary search finds the first entry strictly after now:

def next_spawn_index(timeline, now):
    """timeline is sorted spawn times; return the index of the first spawn strictly after `now`."""
    lo, hi = 0, len(timeline)
    while lo < hi:
        mid = (lo + hi) // 2
        if timeline[mid] <= now:
            lo = mid + 1
        else:
            hi = mid
    return lo

A sorted high-score table works the same way: to find where a new score ranks, binary search for its insertion point instead of scanning every entry.

Exercises

1. Write the sort key Sprites are tuples of (name, y): [("torch", 40), ("player", 70), ("floor_a", 55), ("floor_b", 55)]. Write the key= you’d pass to sorted() for a painter’s-algorithm depth sort. What’s fragile about sorting on y alone when floor_a and floor_b tie?

Answer

key=lambda s: s[1] sorts by y. Because floor_a and floor_b tie at y=55, Python’s stable sorted() will keep whichever one appears first in the input list first in the output — that’s correct within a single frame, but it depends on incidental list order rather than any property of the sprites. If the input list gets rebuilt or filtered between frames, the tie can flip with no in-game reason. A tiebreak key like key=lambda s: (s[1], spawn_order) makes the outcome deterministic regardless of list order.

2. Explain the flicker Two decals, a shadow S (y=50) and a puddle P (y=50), are drawn every frame with sorted(sprites, key=lambda s: s.y) — no tiebreak. Frame 1’s sprite list happens to be [S, P]; after an unrelated enemy despawns and the list gets rebuilt, frame 2’s list happens to become [P, S], even though neither S nor P moved. What changes on screen between the two frames, and how does adding spawn_order as a tiebreak fix it?

Answer

sorted() is stable, but “stable” only means ties keep the order of that call’s input list — it says nothing about consistency across frames. Frame 1 sorts [S, P] (already in order) and draws S then P. Frame 2’s input has quietly become [P, S], so the stable sort keeps P before S and draws P first this time — the draw order of two motionless, same-depth decals flips, which reads on screen as a one-frame flicker or z-fight. Sorting on key=lambda s: (s.y, s.spawn_order) instead makes the order depend only on each sprite’s own properties, not on the incidental order it happened to arrive in this frame’s list, so the tie resolves the same way every time.

3. Trace the timeline binary search Using next_spawn_index above on timeline = [2, 6, 6, 12, 18, 25, 30, 40] with now = 6, trace lo, hi, mid each iteration. What index is returned, and which spawn time does it point to? Why does it skip both 6s?

Answer

Iter	lo	hi	mid	timeline[mid]	Action
1	0	8	4	18	`18 > 6` → `hi = 4`
2	0	4	2	6	`6 <= 6` → `lo = 3`
3	3	4	3	12	`12 > 6` → `hi = 3`

Loop ends (lo == hi == 3), returning index 3, which points to timeline[3] = 12. Both 6s are skipped because the condition timeline[mid] <= now treats a spawn scheduled exactly at now as already handled — the function returns the first spawn strictly after now, matching “what’s next” semantics for a game clock that just ticked past 6.

4. Insertion sort vs. built-in sort, when nearly everything is sorted 200 sprites are sorted from last frame; only 3 moved far enough to pass a neighbor this frame. Compare re-sorting with Python’s built-in sorted() (Timsort) versus insertion_depth_sort above. Why are both fast here, and which one keeps being fast if a level reload suddenly rebuilds the sprite list in arbitrary order?

Answer

Both are close to O(n) on this input: Timsort detects the long already-sorted run among the 197 untouched sprites and only has to merge in the handful that moved; insertion_depth_sort likewise only shifts the few out-of-place sprites past their neighbors, since everyone else fails the while condition immediately. They’re doing the same kind of cheap, localized work, just via different mechanisms. The difference shows up on a bad input: if a level reload rebuilds the sprite list in arbitrary order, insertion sort quietly degrades to its full O(n²) worst case (every element may need to shift all the way across), while Timsort still guarantees O(n log n) no matter how scrambled the input is. Rule of thumb: hand-roll insertion sort only when you can guarantee “nearly sorted, frame to frame”; otherwise let the built-in sort absorb the risk.

Challenge problems

A. Re-sort only the sprites that moved Re-sorting all 1,000 sprites from scratch every frame wastes work when only a handful moved relative to their neighbors. Sketch a way to keep the depth-sorted list updated incrementally, touching only the sprites that changed.

Approach

Track which sprites moved this frame (a small “dirty” set). For each dirty sprite: remove it from the sorted list, then use bisect.insort to reinsert it at the correct position — bisect finds the insertion point in O(log n) by binary search instead of scanning, so the cost per moved sprite is O(log n) to locate plus the cost of shifting elements to make room, versus O(n log n) to re-sort everyone from zero. Sprites that never move (background tiles, static props) never touch the sort again once placed. Caveat: bisect only works correctly on a list that’s fully sorted before and after each call, so you still pay O(n) to physically remove and reinsert into a plain Python list — for very large n with many movers per frame, bucket sprites by row/region and only re-sort within a bucket, or use a data structure built for ordered incremental updates (a sorted skip list, or a balanced-tree-backed sequence).

B. Find the nearest enemy without scanning everyone A homing missile needs the nearest enemy to the player, out of n enemies, every frame. A naive scan checks every enemy’s distance — O(n) per query, fine for 20 enemies, expensive for 2,000 enemies queried by dozens of missiles every frame. Sketch a faster approach that reuses “sort once, query many times.”

Approach

If enemies move slowly relative to how often the query runs, keep an index sorted by one axis (say x). To find the nearest enemy to the player’s x position, binary-search (bisect) for where the player’s x would be inserted — that lands you between the two enemies closest in x, in O(log n). Walk outward from that point in both directions, checking true (x, y) distance, and stop expanding once the remaining candidates’ x-distance alone already exceeds the best distance found so far (their real distance can only be larger). That turns the common case into roughly O(log n) instead of O(n), at the cost of keeping the x-sorted index up to date as enemies move (the same near-sorted, insertion-sort-friendly update as the depth list above). For enemies spread out in open 2D space rather than roughly along a line, a spatial hash grid — bucket enemies by grid cell, check only the player’s cell and its neighbors — generalizes better than a 1D sort.

Going deeper

MIT 6.006 Introduction to Algorithms — lectures on searching and sorting
Stanford CS161 — Design and Analysis of Algorithms — analysis of merge sort, quicksort, and the comparison lower bound
CLRS (Cormen, Leiserson, Rivest, Stein), Introduction to Algorithms — Ch. 2 (insertion sort & the divide-and-conquer paradigm), Ch. 6 (heapsort), Ch. 7 (quicksort), Ch. 8 (the Ω(n log n) comparison-sort lower bound, plus counting/radix sort that beat it)
Sedgewick & Wayne, Algorithms (4th ed.), Princeton — exceptionally clear, code-first treatment of all the sorts in this lesson, with rigorous empirical performance comparisons
Knuth, The Art of Computer Programming, Vol. 3 — “Sorting and Searching” — the definitive, deep-dive treatment; where the comparison-sort lower bound and dozens of sorting variants are analyzed to the last detail
Roughgarden, Algorithms Illuminated, Vol. 1 — approachable, rigorous derivation of merge sort’s O(n log n) bound via recursion trees, pairs well with Stanford CS161
VisuAlgo — Sorting — interactive visualization of sorting algorithms

Searching & Sorting

Linear vs binary search

Binary search, carefully

Sorting overview

The O(n²) sorts: bubble, selection, insertion

Bubble sort

Selection sort

Insertion sort

The O(n log n) sorts: divide and conquer

Merge sort — divide, then combine

Quicksort — partition, then recurse

The O(n log n) lower bound — why you can’t do better

Why stability matters in practice

Timsort — what sorted() actually runs

Complexity

Real-world problem

Exercises

AI Code Critique

🎮 Game Dev: Searching & Sorting

Depth-sorting sprites: the painter’s algorithm

Binary search on a sorted spawn timeline

Going deeper

Timsort — what `sorted()` actually runs