What an algorithm is, explained with sorting cards

TL;DR:

• An algorithm is a precise, finite list of steps that turns an input into a required output.

• Insertion sort builds a sorted hand one card at a time. After each step, the cards you have already handled are in order.

• Correct means two things: the output is sorted, and it contains exactly the same cards you started with.

Pick up five playing cards and sort them in your hand. You do it without thinking, but you follow a method, and that method can be written down so exactly that a computer can run it. A method written that precisely is an algorithm. Sorting cards is a friendly way to see what makes one.

The idea in plain words

An algorithm is a finite list of clear steps that takes an input and produces a required output. Each step must be unambiguous: 'put the cards in a sensible order' is not an algorithm, but 'take the next card and slide it left until the card on its left is smaller' is. And it must end.

A program is an algorithm written in a language a computer can run. The same algorithm can be written in many languages, and many algorithms can solve the same problem, some much faster than others.

Why precision matters

A person fills in gaps from experience. A computer cannot. So you have to state exactly what to compare, what to move, what to do next and when to stop. Writing the steps carefully also lets you reason about whether they always work, not just on the example you tried.

Worked example: sorting a hand of five cards

The input is the hand [7, 3, 9, 2, 5]. The output we want is the same five cards in increasing order. We use insertion sort:

1. Treat the first card as a sorted hand of one.

2. Take the next card from the unsorted part.

3. Compare it with the cards to its left, from the nearest outward. While a card is larger than it, shift that card one place right.

4. Drop the card into the gap.

5. Repeat from step 2 until no cards are left in the unsorted part.

Trace it. A bar marks the end of the sorted part.

Here is the same algorithm in Python.

def insertion_sort(cards):
    for i in range(1, len(cards)):
        card = cards[i]
        j = i - 1
        while j >= 0 and cards[j] > card:
            cards[j + 1] = cards[j]
            j -= 1
        cards[j + 1] = card
    return cards

print(insertion_sort([7, 3, 9, 2, 5]))

The program prints [2, 3, 5, 7, 9]. For i = 3, card is 2 and j starts at 2. The loop shifts 9, then 7, then 3 to the right (j goes 2, 1, 0, then −1), and then 2 lands at position 0. That matches step 3 in the table.

What it means for an algorithm to be correct

A correct sorting algorithm must satisfy two conditions for every input, not just this one. First, the output must be in order. Second, it must be a rearrangement of the input: no card lost, none invented. Insertion sort works because of a fact that stays true at every step. Before handling the next card, all the cards to the left of the bar are already sorted. Inserting one card in the right place keeps that true, and when the bar reaches the end, the whole hand is sorted.

Inputs, outputs and a second algorithm

Writing the input and output down first is half the work. Here the input is a list of numbers and the output is the same numbers in increasing order. With that written, you can compare algorithms fairly, because they all solve the same stated problem.

Another algorithm for the same problem is selection sort: find the smallest card, put it first, then find the smallest of the rest, put it second, and so on. It gives the same output for the same input, but by different steps. Two algorithms can be equally correct and still differ in how many comparisons or moves they need.

How to check your answer

• Sorted? Read the output left to right and confirm each card is no larger than the next.

• Same cards? The output has five items, and the same five values: 2, 3, 5, 7, 9.

• Try edge cases: an empty hand, a hand of one, a hand already in order, a hand in reverse, and a hand with two equal cards.

• Trace by hand first and compare with the program's printed result.

Common mistakes

• Writing steps that depend on judgement, such as 'put it somewhere sensible'.

• Forgetting a stopping condition, so the steps never end.

• Starting the loop at 0 instead of 1. The first card is already a sorted hand of one.

• Using >= instead of > in the comparison. With equal cards that makes extra moves, though the result is still sorted.

• Testing only one input and calling the algorithm correct.

Where you will use it next

Once you can say what an algorithm does and why it is correct, the next question is how fast it is, which is the subject of Big O notation with everyday examples. Binary numbers are how a computer stores the cards in the first place: see binary numbers and why computers use them.

Frequently asked questions

Is a recipe an algorithm?

Roughly yes, if its steps are exact and it finishes. Recipes often rely on human judgement ('until golden'), which a computer cannot do without a precise rule.

Is insertion sort the best way to sort?

No. It is easy to understand and good for short lists, but faster methods exist for large ones. The next articles compare them.