--- title: "Algorithms You'll Actually Use: Sorting, Searching, Recursion, and Beam Search" author: "Pradeep Kumar" published: "2026-10-27T07:35:32.825Z" updated: "2026-10-27T07:35:32.825Z" url: "https://zyvop.com/algorithms-you-ll-actually-use-sorting-searching-recursion-and-beam-search-ji26o" canonical: "https://zyvop.com/algorithms-you-ll-actually-use-sorting-searching-recursion-and-beam-search-ji26o" tags: ["Beam Search","Python","AI Engineer","Dynamic Programming","Algorithms"] --- # Algorithms You'll Actually Use: Sorting, Searching, Recursion, and Beam Search Sorting, searching, recursion, dynamic programming, and beam search explained in plain language, with AI examples like chunking documents and fixing misspelled tool calls. ![Cover image]() An **algorithm** is just a step-by-step recipe for solving a problem. "To find a name in a phone book, open it in the middle, decide which half the name is in, and repeat" is an algorithm. You use them all the time without noticing. You won't be inventing new sorting methods in an AI job. What you will do is choose between tools, spot a familiar pattern when you meet one, and read library documentation without being lost. This post covers the handful of ideas that come up again and again, with AI-flavored examples. It's skippable if you already know them. Here's a test. What does this print, and why would `mystery(40)` take very long to finish? What one-line change would fix that? ```python def mystery(n): if n <= 1: return n return mystery(n - 1) + mystery(n - 2) print([mystery(i) for i in range(8)]) ``` If you said `[0, 1, 1, 2, 3, 5, 8, 13]` and could name the fix (hint: Post 8), skip to Post 18. Otherwise, read on. ## Sorting You'll almost never write a sort yourself. Python's `sorted()` and `list.sort()` use an algorithm called Timsort, which is fast, and **stable**, meaning items that compare as equal stay in their original order. Use `key` to say _what_ to sort by (the function-as-argument idea from Post 6): ```python docs = [ {"title": "Beta", "score": 0.8}, {"title": "Alpha", "score": 0.8}, {"title": "Gamma", "score": 0.9}, {"title": "Delta", "score": 0.5}, ] ranked = sorted(docs, key=lambda d: (-d["score"], d["title"])) print([d["title"] for d in ranked]) # ['Gamma', 'Alpha', 'Beta', 'Delta'] ``` The key is a tuple. It sorts by score from highest to lowest (the minus sign flips the order), and breaks ties alphabetically by title. Putting a tuple in the key is the standard way to sort by several things at once. Stability shows up here: ```python words = ["pear", "fig", "apple", "kiwi", "plum", "date"] print(sorted(words, key=len)) # ['fig', 'pear', 'kiwi', 'plum', 'date', 'apple'] ``` `pear`, `kiwi`, `plum`, and `date` all have four letters, and they stay in the order they started in. One gotcha trips up nearly everyone. `sorted()` returns a new list. `.sort()` changes the list in place and returns `None`: ```python numbers = [3, 1, 2] result = numbers.sort() print(result) # None print(numbers) # [1, 2, 3] ``` If you write `numbers = numbers.sort()`, you've just replaced your list with `None`. ### How sorting works: divide and conquer It's still worth seeing the idea once, because it appears all over computer science. **Merge sort** splits the list in half, sorts each half, and merges the two sorted halves: ```python def merge_sort(items): if len(items) <= 1: return items middle = len(items) // 2 left = merge_sort(items[:middle]) right = merge_sort(items[middle:]) return merge(left, right) def merge(left, right): merged = [] i = j = 0 while i < len(left) and j < len(right): if left[i] <= right[j]: merged.append(left[i]) i += 1 else: merged.append(right[j]) j += 1 merged.extend(left[i:]) merged.extend(right[j:]) return merged ``` Merging two already-sorted lists is easy: keep comparing the front items and take the smaller. The function sorts by calling _itself_ on smaller pieces, which is recursion (more on that below). Why is this fast? Halving a list of a million items takes about 20 splits to get down to single items, and each level of splitting does about a million units of merge work in total. So roughly (number of items) times (number of levels), which people write as **n log n**. A naive method that compares every item to every other grows as n times n, which gets painful quickly. Now the humbling part. On 100,000 random numbers, my merge sort took about 0.2 seconds, and the built-in `sorted` took about 0.02 seconds. The built-in is written in C and heavily tuned. **Don't write your own sort in real code.** Use it to understand the idea, then use `sorted`. One more point: don't sort when you don't need to. If you only want the top few items, a heap (Post 16) is cheaper. If you only want the biggest, use `max`. ## Searching **Linear search** checks items one at a time. It's what `x in some_list` does, and it's fine for short lists. For many lookups, build a `set` or `dict` first (Post 16), and every check becomes almost instant. When your data is **already sorted**, there's a smarter way, **binary search**. Look at the middle item. If it's too small, the target must be in the right half, so ignore the left half. If it's too big, ignore the right half. Repeat: ```python def binary_search(items, target): low, high = 0, len(items) - 1 while low <= high: middle = (low + high) // 2 if items[middle] == target: return middle if items[middle] < target: low = middle + 1 else: high = middle - 1 return -1 ``` Each step throws away half of what's left. For a list of a million items, that means at most about 20 steps, instead of up to a million. In my test on a list of a million numbers, finding an item took 17 steps and confirming a missing one took 20. Binary search is famously easy to get slightly wrong (off-by-one errors in `low`, `high`, and `middle`). So in real code, use Python's built-in `bisect` module: ```python import bisect scores = [10, 20, 30] print(bisect.bisect_left(scores, 25)) # 2 (where 25 would go) bisect.insort(scores, 25) print(scores) # [10, 20, 25, 30] ``` `bisect_left` tells you the position where a value belongs in a sorted list, and `insort` inserts it there while keeping the list sorted. It's handy for things like finding which time range an event falls into. ### Binary search isn't just for lists Here's a trick that's useful in AI work. Suppose you want the largest batch size your GPU can handle without running out of memory. You can't look that up in a list, but you can _test_ a size: it either works or it doesn't. And if size 40 works, so does everything below it. When a yes/no test flips only once like that, binary search finds the boundary in a handful of tries: ```python LIMIT = 37 # pretend the real limit is 37 def fits(batch_size): return batch_size <= LIMIT def largest_batch_that_fits(max_size): low, high, best = 1, max_size, 0 while low <= high: middle = (low + high) // 2 if fits(middle): best = middle low = middle + 1 else: high = middle - 1 return best print(largest_batch_that_fits(512)) # 37 ``` It found the answer in 9 tries, testing 256, 128, 64, 32, 48, 40, 36, 38, and 37, instead of up to 512. When each test means loading a model and waiting a minute, that's a big difference. Searching comes up in AI in another way too. **Vector search** is the problem of finding the stored embeddings closest to a query. The brute-force method is a linear scan of every vector, which we sped up with NumPy in Post 15. When you have millions of vectors, systems use smarter indexes that skip most of the comparisons. We'll see how in Post 52. ## Recursion You met recursion in the last post. A **recursive** function solves a problem by calling itself on a smaller piece. It needs two things: a **base case** where it stops, and a step that moves toward that base case. A good example is flattening a list that contains lists inside lists, like the nested data a model might return: ```python def flatten(items): flat = [] for item in items: if isinstance(item, list): flat.extend(flatten(item)) else: flat.append(item) return flat print(flatten([1, [2, [3, 4]], [[5]], 6])) # [1, 2, 3, 4, 5, 6] ``` The base case is hiding in plain sight: an item that isn't a list gets appended directly, and the function stops going deeper. Recursion has limits. Every call adds to the call stack (Post 16), and Python caps how deep that can go: ```python import sys print(sys.getrecursionlimit()) # 1000 def depth(n): return 0 if n == 0 else 1 + depth(n - 1) depth(5000) # RecursionError: maximum recursion depth exceeded ``` If your data could be extremely deep, rewrite the function as a loop with an explicit stack, like the depth-first search from Post 16. ## Dynamic programming: don't solve the same problem twice Look back at the self-test. `mystery(n)` is the Fibonacci function, and it has a hidden problem. To compute `mystery(5)`, it computes `mystery(4)` and `mystery(3)`. But computing `mystery(4)` _also_ computes `mystery(3)` again, and so on down the tree. The same small problems get solved over and over. Count the calls. Computing `mystery(30)` makes over **2.6 million** calls, and every extra step multiplies the work by about 1.6. Adding 10 to `n` makes it roughly 100 times slower. **Dynamic programming** is the fix: remember each answer the first time you compute it. There are two styles. **Top-down (memoization)** is the easy one. You keep the recursive function and add a cache, which is the one-line fix from Post 8: ```python from functools import cache @cache def fib(n): if n <= 1: return n return fib(n - 1) + fib(n - 2) print(fib(100)) # 354224848179261915075 ``` That answer arrives instantly, because each of the values from 0 to 100 is computed exactly once. **Bottom-up (a table)** fills in the small answers first and builds up, with no recursion at all: ```python def fib_table(n): if n <= 1: return n a, b = 0, 1 for _ in range(n - 1): a, b = b, a + b return b ``` How do you spot a problem that suits this? Three signs: it splits into smaller versions of itself, those smaller versions repeat, and you're after a best, smallest, or count. ### A real example: edit distance Here's a dynamic programming problem you'll genuinely meet. How different are two strings? **Edit distance** counts the fewest single-character changes (insert, delete, or replace) needed to turn one into the other. Turning `"kitten"` into `"sitting"` takes 3. It powers spell checking, fuzzy matching, and de-duplication. And the **word error rate** that's used to score speech recognition systems is the same idea applied to words instead of letters. The smaller problems are "the distance between the first few letters of each string." We fill in a table of those, and it turns out each cell only needs the cell above, the cell to the left, and the one diagonally up-left. That means we only need to remember the previous row: ```python def edit_distance(a, b): previous = list(range(len(b) + 1)) for i, item_a in enumerate(a, start=1): current = [i] for j, item_b in enumerate(b, start=1): cost = 0 if item_a == item_b else 1 current.append( min( previous[j] + 1, # delete current[j - 1] + 1, # insert previous[j - 1] + cost, # replace (or keep) ) ) previous = current return previous[-1] print(edit_distance("kitten", "sitting")) # 3 ``` The work is the length of `a` times the length of `b`, instead of exploding exponentially like the naive recursion. ## Sliding windows: how text gets chunked Here's a pattern you'll use soon. Language models and search systems can't take unlimited text, so long documents get cut into **chunks**. If you cut them cleanly with no overlap, a sentence that straddles the boundary gets split in half and loses its meaning. So chunks usually _overlap_ a little. That's a **sliding window**: a window of fixed size that moves along the data, a few steps at a time. ```python def chunk_words(words, size, overlap): if overlap >= size: raise ValueError("overlap must be smaller than size") step = size - overlap chunks = [] for start in range(0, len(words), step): piece = words[start:start + size] if piece: chunks.append(piece) if start + size >= len(words): break return chunks numbers = list(range(1, 11)) print(chunk_words(numbers, 4, 1)) # [[1, 2, 3, 4], [4, 5, 6, 7], [7, 8, 9, 10]] ``` Each chunk shares one item with the one before it. The window moves forward by `size - overlap` each time, and stops once it has reached the end. The check at the top matters: if the overlap were as big as the window, the step would be zero and the window would never move. We're chunking words here to keep things simple. Real systems usually count tokens, and try to split at sentence boundaries. We'll get into that in Post 54. ## Top-k, again You saw the idea in Post 16: to get the best k items from a big collection, don't sort everything. Keep a small heap, or use `heapq.nlargest`. It matters again in the next section. ## Beam search: how models pick their words Now an algorithm from the heart of AI. A language model writes text one token at a time. At each step it gives a probability to every possible next token. How do you turn that into a sentence? The simplest way is **greedy**: always take the most likely next token. It's fast, but short-sighted. A choice that looks best right now can lead somewhere worse overall. **Beam search** is less hasty. It keeps the best few partial sentences, called the **beam**, at every step. For each one it tries every possible next token, scores all those extended sentences by their total probability, and keeps only the top few. At the end, the best complete sentence wins. Here's a tiny pretend language model, a dictionary of "given this word, here's how likely each next word is": ```python model = { "": {"the": 0.55, "a": 0.45}, "the": {"cat": 0.34, "dog": 0.33, "bird": 0.33}, "a": {"cat": 0.9, "dog": 0.1}, "cat": {"": 1.0}, "dog": {"": 1.0}, "bird": {"": 1.0}, } ``` Greedy takes `the` first (0.55 beats 0.45). But after `the`, the probability is spread thin, with the best next word at only 0.34. So `the cat` has a total probability of 0.55 times 0.34, which is about 0.187. Whereas `a cat` is 0.45 times 0.9, which is 0.405. The sentence that started with the _less likely_ first word is much more likely overall. Greedy can't see that, but beam search can. Here's both, in code. Notice that we add **log probabilities** instead of multiplying probabilities. Multiplying hundreds of small numbers produces a number so tiny the computer rounds it to zero (try `0.1 ** 400` and you'll get `0.0`), while adding their logs stays perfectly stable: ```python import heapq import math def greedy(model, max_len=5): words, log_prob = [""], 0.0 while words[-1] != "" and len(words) < max_len: options = model[words[-1]] word = max(options, key=options.get) log_prob += math.log(options[word]) words.append(word) return words[1:], math.exp(log_prob) def beam_search(model, beam_width=2, max_len=5): beams = [(0.0, [""])] for _ in range(max_len): candidates = [] for log_prob, words in beams: if words[-1] == "": candidates.append((log_prob, words)) continue for word, p in model[words[-1]].items(): candidates.append((log_prob + math.log(p), words + [word])) beams = heapq.nlargest(beam_width, candidates) if all(words[-1] == "" for _, words in beams): break best_log_prob, best_words = beams[0] return best_words[1:], math.exp(best_log_prob) print(greedy(model)) # (['the', 'cat', ''], 0.187) print(beam_search(model, beam_width=2)) # (['a', 'cat', ''], 0.405) ``` With a beam width of 1, beam search is the same as greedy. With a width of 2, it keeps both `the` and `a` alive after the first step, and the better ending wins. Look at what's inside: `heapq.nlargest` picking the top few candidates at every step. That's the top-k pattern from Post 16, doing real work. Two honest notes. A wider beam costs more, since you extend more candidates at every step, and it's not always better in practice. And chat models today often generate text by _sampling_ instead, using settings like temperature, rather than beam search. Beam search has long been used for tasks like translation and speech recognition, where you want the single most likely output. Either way, understanding it shows you what's really happening when a model "chooses" its next word. ## Mini project: a "did you mean?" for tool calls Here's a real problem in agent apps. A model is asked to call a tool, and it spells the tool's name slightly wrong, such as `get_wether` instead of `get_weather`. Your code looks up the name, finds nothing, and crashes. A friendlier approach is to find the closest valid names and tell the model, so it can try again. That's edit distance, plus a heap, plus the error handling from Post 11. Create `did_you_mean.py`: ```python import difflib import heapq def edit_distance(a, b): """Fewest single-item edits (insert, delete, replace) to turn a into b.""" previous = list(range(len(b) + 1)) for i, item_a in enumerate(a, start=1): current = [i] for j, item_b in enumerate(b, start=1): cost = 0 if item_a == item_b else 1 current.append( min( previous[j] + 1, # delete current[j - 1] + 1, # insert previous[j - 1] + cost, # replace (or keep) ) ) previous = current return previous[-1] def did_you_mean(name, valid_names, max_distance=2, k=3): scored = [(edit_distance(name, valid), valid) for valid in valid_names] close = [pair for pair in scored if pair[0] <= max_distance] return [valid for distance, valid in heapq.nsmallest(k, close)] class ToolNotFoundError(Exception): pass def call_tool(name, tools): if name not in tools: suggestions = did_you_mean(name, list(tools)) hint = f" Did you mean: {', '.join(suggestions)}?" if suggestions else "" raise ToolNotFoundError(f"Unknown tool {name!r}.{hint}") return tools[name]() tools = { "get_weather": lambda: "Sunny, 24 degrees", "get_time": lambda: "10:30", "search_web": lambda: "3 results", "send_email": lambda: "Sent", "set_timer": lambda: "Timer set", } print(edit_distance("kitten", "sitting")) print(did_you_mean("get_wether", list(tools))) print(did_you_mean("set_time", list(tools))) print(difflib.get_close_matches("get_wether", list(tools), n=3, cutoff=0.6)) for name in ["get_weather", "get_wether", "send_mail", "launch_rocket"]: try: print(name, "->", call_tool(name, tools)) except ToolNotFoundError as error: print(name, "-> error:", error) reference = "the cat sat on the mat".split() heard = "the cat sit on mat".split() print(f"word error rate: {edit_distance(reference, heard) / len(reference):.2f}") ``` You should see: ```go 3 ['get_weather'] ['get_time', 'set_timer'] ['get_weather', 'get_time', 'set_timer'] get_weather -> Sunny, 24 degrees get_wether -> error: Unknown tool 'get_wether'. Did you mean: get_weather? send_mail -> error: Unknown tool 'send_mail'. Did you mean: send_email? launch_rocket -> error: Unknown tool 'launch_rocket'. word error rate: 0.33 ``` A few things to notice: - **The same** `edit_distance` **works on letters and on words.** In the last lines we pass in lists of words and get a word error rate: 2 edits (one replaced word, one missing word) over 6 words, which is 0.33. - **The error message is written for the model.** In a real agent loop, you'd feed that "Did you mean..." text back so the model can correct itself, the same trick as validating replies in Post 10. - `set_time` **returns two suggestions** that are both one edit away, with ties broken alphabetically by the heap. - `difflib` **is the shortcut.** Python's standard library has `difflib.get_close_matches`, which does a similar job. It uses a different similarity measure, so its results aren't identical: it returned `get_time` and `set_timer` as extra candidates for `get_wether`. Neither is "right". Pick the one that suits your data. ### Make it yours 1. Add a test file using the techniques in Post 13. Include a property-based test that checks `edit_distance(a, b) == edit_distance(b, a)` and that `edit_distance(a, a) == 0`. 2. Add `@cache` to a recursive version of edit distance and compare it with the table version. 3. Make suggestions ignore case and underscores. 4. Compute the word error rate between two real sentences of your own. 5. Time `did_you_mean` against `difflib` with 10,000 valid names. ## Practice About 20 minutes of real effort on each before asking for help. 1. Sort a list of dictionaries by two keys: one descending and one ascending. 2. Write a binary search that returns where a value _would_ be inserted, then compare it with `bisect_left` on lots of random lists. 3. Write your own version of "largest batch that fits", using a `fits` function that you invent. 4. Write a recursive function that returns how deeply a list is nested. 5. Take a slow recursive function and speed it up with `@cache`. Time it before and after. 6. Write a function that returns the word error rate between two sentences. 7. Extend `chunk_words` so it chunks by sentences instead of words. Write a test that every word appears in at least one chunk. 8. Change the toy model in the beam search example so that greedy and beam search agree, then so they disagree. Try beam widths of 1, 2, and 3. Then ask an AI tutor to review your answers, and don't let it rewrite them. ## What to take away - Use `sorted` with a `key`. Sorting is stable, and a tuple key sorts by several things at once. - Binary search needs sorted data and takes about 20 steps for a million items. It also works for any yes/no test that flips just once. - Recursion needs a base case. For deep problems, switch to a loop with a stack. - Dynamic programming means not solving the same problem twice. Add `@cache`, or fill in a table. - Edit distance measures how different two strings are, and powers fuzzy matching. - Sliding windows with overlap are how long text gets chunked. - Beam search keeps the best few partial answers at every step, which beats greedy choices that look good now and turn out badly later. * * * **Previous:** Post 16, _Data Structures for AI Engineers_ **Next in the series:** Post 18, _Big-O Without the Fear_, where we put proper names on all this "fast versus slow" talk, and learn why complexity matters for vector search and batching.