Sorting and Searching Algorithms

Why these algorithms matter

Two of the most common jobs in all of computing are searching (finding a particular item) and sorting (putting items into order). Your phone searches contacts, a website sorts products by price, a game ranks high scores. Behind each of these is an algorithm — a precise sequence of steps. The fascinating thing is that for the same job there are many different algorithms, and some are dramatically faster than others. Learning to compare them is a core skill in computer science.

If the word algorithm is new, start with What Is an Algorithm?. Here we'll look at specific, named algorithms and, importantly, how to measure which is better.

Searching: linear search

Imagine a list of numbers and you want to know whether 37 is in it. The most obvious method is linear search: start at the first item and check each one in turn until you find your target or run out of items.

function linearSearch(list, target):
    for each item in list:
        if item == target:
            return "found"
    return "not found"

Linear search is wonderfully simple and it works on any list — sorted or not. Its weakness is speed. If the target is the last item (or isn't there at all), you have to check every item. For a list of 1,000 items that's up to 1,000 checks; for a million items, up to a million. The work grows in direct proportion to the list size.

Searching: binary search

Now suppose the list is sorted in order. We can do something much cleverer with binary search. Instead of starting at the beginning, we start in the middle and ask: is the target equal to, less than, or greater than the middle item?

• If it's equal, we're done.
• If the target is smaller, it must be in the left half, so we throw away the right half.
• If the target is larger, it's in the right half, so we throw away the left half.

Then we repeat on the half that's left, checking its middle, and so on. Each step halves the amount of list we still have to search.

function binarySearch(sortedList, target):
    low = 0
    high = length(sortedList) - 1
    while low <= high:
        mid = (low + high) / 2     (rounded down)
        if sortedList[mid] == target:
            return "found"
        else if sortedList[mid] < target:
            low = mid + 1           (search right half)
        else:
            high = mid - 1          (search left half)
    return "not found"

This is the same trick you use when guessing a number between 1 and 100: guess 50, get told "higher" or "lower," then guess the middle of what's left. The power is enormous. To search 1,000 sorted items, linear search might need 1,000 checks, but binary search needs only about 10, because you can halve 1,000 about ten times (2¹⁰ = 1,024). For a million items it's only about 20 checks. The catch: the list must be sorted first, which is exactly why sorting matters.

Sorting: bubble sort

To put a list in order, one of the simplest methods is bubble sort. The idea: walk through the list comparing each pair of neighbours, and swap them if they're in the wrong order. Big values gradually "bubble" up to the end. You repeat these passes until you go all the way through without making a single swap, which means the list is sorted.

function bubbleSort(list):
    repeat:
        swapped = false
        for i from 0 to length(list) - 2:
            if list[i] > list[i + 1]:
                swap list[i] and list[i + 1]
                swapped = true
    until swapped == false

Let's sort [5, 2, 4, 1] step by step in the first pass:

• Compare 5 and 2 → swap → [2, 5, 4, 1]
• Compare 5 and 4 → swap → [2, 4, 5, 1]
• Compare 5 and 1 → swap → [2, 4, 1, 5]

After one pass the biggest number (5) has bubbled to the end. Repeat the passes and the list becomes [1, 2, 4, 5]. Bubble sort is easy to understand but slow, because in the worst case it makes roughly n passes over n items.

Sorting: selection sort

Another simple sort is selection sort. The idea: find the smallest item in the list and put it first. Then find the smallest item in the rest of the list and put it second. Keep going, each time selecting the smallest of what remains.

function selectionSort(list):
    for i from 0 to length(list) - 1:
        smallest = i
        for j from i + 1 to length(list) - 1:
            if list[j] < list[smallest]:
                smallest = j
        swap list[i] and list[smallest]

Sorting [29, 10, 14, 37]: the smallest is 10, so swap it to the front → [10, 29, 14, 37]. The next smallest (of the rest) is 14 → [10, 14, 29, 37]. Already sorted. Selection sort makes fewer swaps than bubble sort but still has to scan the remaining list every time.

Measuring speed: Big-O notation

Saying one algorithm "feels faster" isn't good enough in computer science. We need a fair way to compare them that doesn't depend on a particular computer's speed. That's what Big-O notation is for. It describes how the number of steps grows as the input gets bigger.

• O(1) — constant. The work doesn't grow with the data (e.g. reading the first item).
• O(log n) — logarithmic. Work grows very slowly; the data can double for only one extra step. Binary search is O(log n).
• O(n) — linear. Work grows in step with the data. Linear search is O(n).
• O(n²) — quadratic. Work grows with the square of the data; doubling the data quadruples the work. Bubble sort and selection sort are O(n²).

The difference is huge at scale. For a million items, an O(n) algorithm does about a million steps, an O(n²) algorithm does about a trillion, but an O(log n) algorithm does only about 20. This is why choosing the right algorithm can be the difference between a program that answers instantly and one that takes hours. Real programming languages use highly optimised sorts (like quicksort or mergesort, both far faster than O(n²)) for exactly this reason.

Putting it together

Notice how searching and sorting connect: binary search is lightning fast, but it requires sorted data. So there's often a trade-off — spend effort sorting once, then enjoy fast searches many times. Deciding when that trade-off is worth it is the kind of judgement that separates writing code from writing good code. And when your sort produces the wrong order, the methodical thinking of debugging is how you trace which comparison went wrong.

Try it yourself

Make these algorithms real:

• 🃏 Grab a shuffled set of playing cards. Sort them by hand using bubble sort (only ever swap neighbours) and then again using selection sort (always pull out the smallest remaining card). Count the moves each takes — which felt more efficient?
• 🔢 Play the number-guessing game with a friend (1–100). Guess using binary search (always halve the range) and see how you reliably win in 7 guesses or fewer, since 2⁷ = 128.
• 💻 In a language like Python, write linearSearch and binarySearch, then test both on a sorted list of 1,000 numbers. Add a counter to each and compare how many checks they make.
• 📈 Sketch the curves for O(log n), O(n), and O(n²) on the same axes. Seeing how steeply O(n²) climbs makes the cost of a slow algorithm unforgettable.

Master searching, sorting, and Big-O, and you've taken a real step from "someone who can code" toward "someone who thinks like a computer scientist."