Skip to content

Expert · Algorithms, data structures and testing · topic 46 of 50 · 35 min

Recursion and sorting algorithms

Explanation

Recursion means a function calls itself on a smaller piece of the problem until it reaches a case simple enough to answer directly, called the base case. Sorting algorithms put items in order: simple ones like selection sort take O(n^2) steps, while merge sort uses recursion to sort in O(n log n). In real work you use Python's built-in sorted(), which is fast, stable and well tested.

A function that calls itself

A recursive function solves a problem by solving a smaller version of the same problem. Every recursive function needs two parts. The base case is the smallest problem, answered directly without another call. The recursive case breaks the problem into a smaller one and calls the function again.

Think of it like this: You are in a dark cinema hall and want to know your row number. You ask the person in front, "Which row are you in?" They ask the person in front of them, and so on. The person in the first row knows the answer: 1 (the base case). Each answer comes back one step at a time, each person adding 1, until it reaches you.
python
def factorial(n):
    if n <= 1:              # base case
        return 1
    return n * factorial(n - 1)   # recursive case: a smaller problem

print(factorial(5))   # 5 * 4 * 3 * 2 * 1 = 120
factorial(5) waits for factorial(4), which waits for factorial(3)... down to factorial(1), then the answers multiply back up.
python
def sum_digits(n):
    if n < 10:              # one digit left
        return n
    return n % 10 + sum_digits(n // 10)

print(sum_digits(2024))   # 2 + 0 + 2 + 4 = 8
n % 10 is the last digit; n // 10 removes it, leaving a smaller number.

Forgetting the base case: RecursionError

Each call waits in memory on the call stack (the list of functions that are still running) until the call it made returns. Without a base case the calls never stop. Python protects itself with a limit of about 1000 nested calls and raises RecursionError.

python
def countdown(n):
    return countdown(n - 1)   # no base case!

try:
    countdown(3)
except RecursionError as err:
    print("Stopped:", err)
The calls go 3, 2, 1, 0, -1, ... until Python stops them.
Careful: Python does not optimise deep recursion. For very long chains (like walking a list of 100,000 items) use a loop instead. Recursion is best when the problem naturally splits into smaller parts, as in merge sort, folders inside folders, or family trees.

Selection sort: simple but slow

Selection sort finds the smallest item and swaps it to the front, then finds the smallest of the rest and puts it second, and so on. For each of the n positions it scans the remaining items, so it does about n x n / 2 comparisons: O(n^2).

python
def selection_sort(items):
    items = list(items)                 # work on a copy
    for i in range(len(items)):
        smallest = i
        for j in range(i + 1, len(items)):
            if items[j] < items[smallest]:
                smallest = j
        items[i], items[smallest] = items[smallest], items[i]
    return items

print(selection_sort([64, 25, 12, 22, 11]))
Easy to understand, but 10,000 items need about 50 million comparisons.

Merge sort: divide and conquer

  1. Base case: a list with 0 or 1 items is already sorted.
  2. Split the list into two halves.
  3. Sort each half by calling merge sort on it (recursion).
  4. Merge the two sorted halves: repeatedly take the smaller front item of the two.
python
def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])     # whatever is left over
    result.extend(right[j:])
    return result

def merge_sort(items):
    if len(items) <= 1:
        return list(items)
    mid = len(items) // 2
    return merge(merge_sort(items[:mid]), merge_sort(items[mid:]))

print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
Merging two sorted lists is fast because you only ever compare the two front items.

Why O(n log n)? Halving the list again and again gives about log n levels (20 levels for a million items). At each level, merging touches all n items once. So the total is n times log n, far less than n x n for big lists.

AlgorithmBig-ONotes
Bubble sort / selection sortO(n^2)Good for learning, too slow for real data
Merge sortO(n log n)Always fast, needs extra memory for merging
Timsort (Python's sorted)O(n log n)Very fast on real data, even faster on nearly sorted lists
Tip: In real projects, use sorted(items) or items.sort(). Python uses Timsort, a clever mix of merge sort and insertion sort. It is stable, which means equal items keep their original order, so you can sort by one key and then another safely.
python
orders = [("Riya", 450), ("Kabir", 120), ("Sana", 450), ("Dev", 300)]
by_amount = sorted(orders, key=lambda order: order[1], reverse=True)
print(by_amount)   # Riya stays before Sana: Timsort is stable
key= says what to sort by. Writing your own sort is for learning and interviews.

Watch the lesson

Recursion and sorting algorithms · 1/7

Recursion and sorting

In this lesson you will learn recursion, and use it to understand how fast sorting algorithms work.

Prefer a video by a teacher? Find free videos on “python recursion and merge sort explained” on YouTube ↗

In real life: Sorting delivery orders and walking folders

A grocery delivery app sorts thousands of orders by delivery time before assigning riders; it simply calls sorted() with a key, because Timsort is fast and reliable. Recursion shows up elsewhere in the same app: the product catalogue has categories inside categories (Food > Snacks > Namkeen), and a recursive function counts every product in a category and all its sub-categories.

python
catalogue = {
    "name": "Food",
    "products": 2,
    "children": [
        {"name": "Snacks", "products": 5, "children": [
            {"name": "Namkeen", "products": 12, "children": []},
        ]},
        {"name": "Drinks", "products": 7, "children": []},
    ],
}

def count_products(category):
    total = category["products"]
    for child in category["children"]:
        total += count_products(child)      # same problem, smaller piece
    return total

print(count_products(catalogue))   # 2 + 5 + 12 + 7 = 26
The base case is a category with no children: the loop simply does nothing.

Practice (0/3 done)

Task 1 · Code · Python

Write a RECURSIVE function sum_digits(n) that returns the sum of the digits of a non-negative whole number. sum_digits(2024) is 8. Base case: a number below 10 is its own digit sum.

Task 2 · Code · Python

Write merge(left, right). Both lists are already sorted. Return ONE new sorted list with all items from both. Do not call sorted() or .sort(): walk both lists with two positions.

Task 3 · Code · Python

Write merge_sort(items) that returns a NEW sorted list using merge sort: base case for 0 or 1 items, split in half, sort each half recursively, then merge. Do not change the input list. A merge(left, right) helper is already written for you.

Quick quiz

Question 1

1.What is the base case in a recursive function?

Question 2

2.What happens if a recursive function has no base case?

Question 3

3.What is the Big-O of merge sort?

Question 4

4.What should you use to sort data in a real project?

Question 5

5.What does it mean that Python's sort is stable?

Read more (free)

Pass the quiz (60% or more) or mark this topic as done when you are ready.

Your progress is saved on this device only.

Next: Stacks and queues →

← Previous: Big-O and searching