How Algorithms Work, Sorting and Searching Lesson

Lesson by Adnan, computer science lecturer  ·  aitrendblend editorial team  ·  Computer Science Education  ·  October 2026  ·  Reading time about 23 minutes

How Algorithms Work
Sorting and Searching

Who this lesson is for and how to use it

This is the fifth lesson in our Computer Science Education series. At the end of How a Computer Works we promised a unit on algorithms, and this is it. Students who did How the Internet Works have already met one famous algorithm, Dijkstra’s shortest path method for routing, and students who did How AI Learns met another, gradient descent. This lesson steps back and asks what all algorithms have in common, and how we compare them.

The lesson suits grades nine to twelve and first year college students, and it fits naturally before or alongside a first programming course. No coding is needed for the labs. The Python code at the end implements every algorithm in the lesson for students ready to read real code.

Learning objectives

After three periods, a student should be able to do the following five things without notes.

1. Define an algorithm and give an everyday example with clear, finite steps.
2. Describe how bubble sort, insertion sort, merge sort and quick sort work in words.
3. Explain how binary search works and why it needs sorted data.
4. Use Big O notation to compare log n, n, n log n and n squared growth.
5. Choose a sensible algorithm for a small or large, random or nearly sorted list and justify the choice.

What an algorithm is

An algorithm is a precise list of steps that solves a problem and always finishes. A recipe is close, but recipes allow vague steps like season to taste. An algorithm cannot. Every step must be exact enough that someone, or something, with no common sense could follow it and get the right answer every time. That is exactly the kind of instruction the CPU from our first lesson can carry out.

The word itself has a history worth telling the class. In the ninth century the mathematician Muhammad ibn Musa al-Khwarizmi worked at the House of Wisdom in Baghdad. His book on calculating with Hindu Arabic numerals was translated into Latin, where his name became Algoritmi, and over the centuries that name turned into the word algorithm. Another of his books, on solving equations, gave us the word algebra. The oldest algorithm still in everyday use is even older. Euclid’s method for finding the greatest common divisor of two numbers appears in his Elements, written around 300 BCE, and computers still run it today.

Three questions help students judge any algorithm. Is it correct, meaning it always gives the right answer? Does it finish? And how much work does it need as the problem gets bigger? The rest of this lesson is mostly about the third question, because that is where the surprises live.

Sorting, the problem every computer solves constantly

Sorting sounds like a small task, but computers do it all the time. Contacts are sorted by name, search results by relevance, messages by time, and shops sort products by price. Sorted data is also what makes fast searching possible, as students will see in Lab 2. Here are the five methods in the lab, described the way you might explain them to a class holding playing cards.

Bubble sort walks along the row comparing each pair of neighbours and swapping them if they are in the wrong order. After one pass the largest value has bubbled to the end. Repeat until a full pass makes no swaps. Selection sort scans for the smallest remaining value and moves it to the front, then repeats on what is left. Insertion sort picks up each card in turn and slides it left until it sits in the right place, exactly how most people sort a hand of cards.

The last two are cleverer. Merge sort splits the list in half, sorts each half the same way, then merges the two sorted halves by repeatedly taking the smaller front item. John von Neumann described it in 1945, the same year as the stored program report from our first lesson. Quick sort, invented by Tony Hoare in 1959, picks one value called the pivot, moves everything smaller to its left and everything bigger to its right, then sorts each side the same way.

Run each algorithm on 40 bars and note the comparison count, then press Race all five, which runs every method on the current bars and charts the work. On random data merge sort and quick sort usually need around two hundred comparisons while bubble sort and selection sort need around seven or eight hundred. Now press Nearly sorted and race again. Insertion sort suddenly wins, because each bar only slides a short distance. Press Reverse order and watch quick sort, with the simple pivot rule used here, slow down badly. No algorithm is best at everything, which is one of the most useful lessons in computer science.

Searching, finding a needle quickly

Searching is the other everyday job. The simplest method, linear search, checks every item from the start until it finds the target. It works on any list, sorted or not, but in the worst case it checks everything. For a list of a million names, that can mean a million checks.

If the list is sorted, there is a dramatically better way. Binary search looks at the middle item. If the target is bigger, the whole left half can be thrown away, and if it is smaller, the right half goes. Then it repeats on the half that is left. Every step cuts the problem in half. The idea was described as early as 1946 by John Mauchly, one of the builders of the ENIAC computer, though it is famous among programmers for being easy to explain and surprisingly easy to code with a small mistake.

With 31 items, binary search never needs more than 5 checks. Double the list to 63 and it needs at most 6. A sorted list of a million items needs at most 20, and the entire population of the world could be searched in about 33. This is why phone books, dictionaries and databases keep their data sorted. Sorting costs effort once, and every search afterwards becomes almost free.

Play against binary search

The guessing game below is binary search in disguise. The computer picks a secret number from 1 to 100 and tells you whether each guess is too high or too low. Play it once on your own, then press Watch the computer play. It always guesses the middle of what is still possible, and it never needs more than seven guesses, because two to the power seven is 128, which is more than 100.

Halving is a superpower. Twenty questions can pick one item out of a million, if every question cuts the possibilities in half.From this lesson, period two

Big O, measuring how work grows

Timing a program with a stopwatch tells you about one computer on one day. Computer scientists want something more lasting, a way to describe how the work grows as the input grows. That description is called Big O notation. The notation itself came from the German mathematician Paul Bachmann in 1894, and Donald Knuth made it standard in computer science in the 1970s.

The idea is to count steps and ignore small details. Linear search does about n steps for n items, written O(n). Binary search does about log n, written O(log n). Bubble sort compares roughly every pair, about n squared over two comparisons, which is O(n²). Merge sort splits the list log n times and does about n work at each level, giving O(n log n).

Drag the slider below from ten items to a hundred thousand. The bars use a scale where each step to the right means ten times more work, and the last column assumes a computer doing a million steps every second. Watch what happens to the n squared row.

At a thousand items every row finishes in well under a second, which is why beginners do not notice the difference. At a hundred thousand items an n log n algorithm still finishes in under two seconds, while an n squared one needs nearly three hours. Real systems sort millions or billions of records, where the gap becomes the difference between a result in seconds and a result that never arrives. A computer a hundred times faster cannot rescue a bad algorithm for long, because the next doubling of the data eats the improvement.

Algorithms in the real world

Students meet these ideas every day without noticing. Python’s built in sort uses Timsort, created by Tim Peters in 2002, a hybrid that runs insertion sort on short stretches and merge sort to combine them, precisely because insertion sort is so fast on nearly sorted data, the effect students saw in Lab 1. Databases keep indexes sorted in tree structures so that finding a record among billions takes only a few dozen steps, the same halving trick as binary search.

Map apps use shortest path algorithms like the Dijkstra method from our internet lesson. Search engines combine sorting, searching and ranking to answer a query in a fraction of a second. And the AI systems from our neural network lesson are themselves algorithms, gradient descent repeated billions of times, which is why researchers care so much about the efficiency of every step. Our article on generalization bounds for shallow networks shows the kind of careful analysis researchers apply to learning algorithms, a long way beyond this lesson but built on the same habit of measuring how work grows.

Misconceptions students bring to class

• An algorithm is the same as a program. An algorithm is the idea, a precise method. A program is that method written in a particular language for a particular machine.
• Faster computers make algorithm choice unimportant. Better hardware improves speed by a fixed factor, but a worse growth rate loses as soon as the data grows.
• The fastest algorithm is always best. Simple algorithms are easier to get right and can be faster on small or nearly sorted inputs.
• Binary search works on any list. It only works when the list is sorted, because the order is what tells you which half to throw away.
• Big O tells you exact time. It describes growth, not seconds. Two O(n) algorithms can differ in speed by a large constant factor.

Where this lesson simplifies the truth

The labs count comparisons and moves, which is a fair way to compare methods but not the same as running time on a real machine, where memory access patterns and caches from our first lesson matter a great deal. Quick sort in the lab uses the simplest pivot rule, the last item, which is why reversed input hurts it. Real implementations choose pivots more cleverly and are among the fastest sorts in practice.

Big O also hides a lot. It ignores constant factors and small inputs, and computer scientists distinguish between best, average and worst cases, which this lesson mentions only briefly. Merge sort also needs extra memory for merging, a cost the lab does not show. These details matter for professionals, but they refine the picture rather than change it.

Bringing it all together

The main achievement of this lesson is a habit of mind. Students now ask not only whether a method works but how much work it needs, and how that work grows. They have seen bubble sort and merge sort produce the same answer with very different effort, watched binary search beat linear search by a margin that grows with every doubling of the list, and learned a compact notation for describing the difference.

The conceptual shift is from thinking of computers as fast to thinking of methods as efficient. A computer runs whatever steps it is given, and as our first lesson showed, it never gets bored. The intelligence lies in choosing steps that do not waste effort. That choice is what separates a search that answers instantly from one that never finishes.

The ideas reach into every other lesson in the series. Routing on the internet uses shortest path algorithms. Password security in our cybersecurity lesson is really a Big O argument, making the attacker’s search space so large that no algorithm can finish. And training a neural network is an algorithm whose efficiency decides whether a model can be built at all.

The lesson has honest limits. It leaves out recursion as a formal topic, data structures such as trees and hash tables, and the analysis of average cases. Teachers with stronger classes can extend period three by having students implement binary search themselves and hunt for the famous off by one bugs, while teachers without computers can run the entire unit with playing cards and the human sorting game.

A natural next lesson is data structures, the ways of organizing information that make these algorithms possible. For now, the students who sorted exam papers by hand at the start can explain exactly why the one who split the pile and merged the halves finished first.

Companion Python code for the classroom

The program below implements every algorithm in the lesson in plain Python. It sorts 200 random numbers with bubble, insertion, merge and quick sort while counting comparisons, compares linear and binary search on the result, plays the guessing game perfectly and checks the worst case over every secret number, and prints a table showing how log n, n log n and n squared grow.

# How Algorithms Work, companion code for the aitrendblend lesson
# Runs on any Python 3 installation. No extra libraries needed.
import math
import random

random.seed(11)


# Part 1. Sorting algorithms that count their comparisons
def bubble_sort(a):
    a, comps = a[:], 0
    for end in range(len(a) - 1, 0, -1):
        swapped = False
        for i in range(end):
            comps += 1
            if a[i] > a[i + 1]:
                a[i], a[i + 1] = a[i + 1], a[i]
                swapped = True
        if not swapped:          # already sorted, stop early
            break
    return a, comps


def insertion_sort(a):
    a, comps = a[:], 0
    for i in range(1, len(a)):
        key, j = a[i], i - 1
        while j >= 0:
            comps += 1
            if a[j] <= key:
                break
            a[j + 1] = a[j]      # shift the bigger card right
            j -= 1
        a[j + 1] = key
    return a, comps


def merge_sort(a):
    comps = 0

    def sort(xs):
        nonlocal comps
        if len(xs) <= 1:
            return xs
        mid = len(xs) // 2
        left, right = sort(xs[:mid]), sort(xs[mid:])
        out, i, j = [], 0, 0
        while i < len(left) and j < len(right):
            comps += 1
            if left[i] <= right[j]:
                out.append(left[i]); i += 1
            else:
                out.append(right[j]); j += 1
        return out + left[i:] + right[j:]

    return sort(a[:]), comps


def quick_sort(a):
    a, comps = a[:], 0

    def sort(lo, hi):
        nonlocal comps
        if lo >= hi:
            return
        pivot, p = a[hi], lo
        for i in range(lo, hi):
            comps += 1
            if a[i] < pivot:
                a[i], a[p] = a[p], a[i]
                p += 1
        a[p], a[hi] = a[hi], a[p]   # pivot lands in its final place
        sort(lo, p - 1)
        sort(p + 1, hi)

    sort(0, len(a) - 1)
    return a, comps


# Part 2. Searching
def linear_search(xs, target):
    for steps, x in enumerate(xs, start=1):
        if x == target:
            return steps - 1, steps
    return -1, len(xs)


def binary_search(xs, target):
    lo, hi, steps = 0, len(xs) - 1, 0
    while lo <= hi:
        steps += 1
        mid = (lo + hi) // 2
        if xs[mid] == target:
            return mid, steps
        if xs[mid] < target:
            lo = mid + 1           # throw away the left half
        else:
            hi = mid - 1           # throw away the right half
    return -1, steps


# Part 3. The guessing game, played perfectly
def guess_number(secret, low=1, high=100):
    guesses = []
    while True:
        g = (low + high) // 2
        guesses.append(g)
        if g == secret:
            return guesses
        if g < secret:
            low = g + 1
        else:
            high = g - 1


# Smoke test
if __name__ == "__main__":
    data = random.sample(range(1, 1001), 200)
    print("Comparisons to sort 200 random numbers")
    results = {}
    for name, fn in [("bubble", bubble_sort), ("insertion", insertion_sort),
                     ("merge", merge_sort), ("quick", quick_sort)]:
        out, comps = fn(data)
        results[name] = out
        print(f"  {name:<10} {comps:>6}")

    sorted_data = sorted(data)
    target = sorted_data[150]
    print("\nLinear search steps:", linear_search(sorted_data, target)[1])
    print("Binary search steps:", binary_search(sorted_data, target)[1])

    print("\nGuessing 73 between 1 and 100:", guess_number(73))
    worst = max(len(guess_number(s)) for s in range(1, 101))
    print("Worst case over every secret number:", worst, "guesses")

    print("\nGrowth of the work as n grows")
    for n in (10, 1_000, 1_000_000):
        print(f"  n={n:>9,}  log n={math.ceil(math.log2(n)):>3}  n log n={round(n*math.log2(n)):>12,}  n^2={n*n:>16,}")

    assert all(r == sorted_data for r in results.values())
    assert binary_search(sorted_data, target)[0] == 150
    assert worst == 7
    print("\nAll checks passed.")

When you run it, bubble sort should need around twenty thousand comparisons while merge sort needs around thirteen hundred, binary search should take 7 steps where linear search takes over 150, the guessing game should never need more than 7 guesses, and the final line should report that all checks passed. A good extension task is to add selection sort and predict its comparison count before running it.

Check your understanding

Six questions cover the whole lesson. Choose an answer for each and press Check answers to see which were right, with a short explanation for each.

Frequently asked questions

Related reading on aitrendblend