Why Does Merge Sort Use len(arr) <= 1 Instead of len(arr) == 1?

[Rajeev Bagra]

Many beginners learn that the base case of Merge Sort is:

def mergesort(arr):
    if len(arr) <= 1:
        return

At first glance, they often wonder:

Why do we write <= 1 instead of == 1?

After all, Merge Sort is supposed to stop when only one element remains.

The answer lies in understanding how recursion works and why an empty list should also be considered a completed problem.

---

What Is the Base Case?

Every recursive function needs a condition that tells it when to stop calling itself.

For Merge Sort, the base case is:

if len(arr) <= 1:
    return

This means:

If the list contains zero or one element, there is nothing left to sort.

---

Case 1: A List with One Element

Suppose the function receives:

arr = [42]

Python calculates:

len(arr)

which returns:

1

A list containing one element is already sorted.

There is nothing to divide further.

Therefore Merge Sort immediately returns.

---

Case 2: An Empty List

Now suppose the function receives:

arr = []

Python calculates:

len(arr)

which returns:

0

An empty list is also considered sorted because there are no elements to arrange.

Again, Merge Sort should stop immediately.

---

What Happens If We Use == 1?

Suppose the base case were written as:

if len(arr) == 1:
    return

Now imagine someone accidentally calls:

mergesort([])

Python evaluates:

len(arr) == 1

which becomes:

0 == 1

The result is:

False

Since the condition is false, Merge Sort continues instead of stopping.

---

The Problem Begins

Python computes:

middle = len(arr) // 2

Since the list is empty:

middle = 0

The function creates:

left = []
right = []

Then recursively calls:

mergesort(left)
mergesort(right)

But both left and right are still empty lists.

Exactly the same thing happens again.

---

Visualizing the Recursion

Instead of stopping, the function keeps calling itself forever.

mergesort([])
      ↓
mergesort([])
      ↓
mergesort([])
      ↓
mergesort([])
      ↓
...

Eventually Python reaches its recursion limit and raises:

RecursionError: maximum recursion depth exceeded

---

Why <= 1 Solves the Problem

The condition:

if len(arr) <= 1:
    return

covers both possible stopping cases.

Length = 0   ✓ Stop
Length = 1   ✓ Stop
Length = 2   ✗ Continue
Length = 3   ✗ Continue
Length = 4   ✗ Continue

As soon as the list becomes empty or contains a single element, recursion ends.

---

Why Use <= Instead of ==?

Using:

if len(arr) <= 1:

makes the function more robust.

Even if another programmer accidentally passes an empty list, Merge Sort behaves correctly without producing an error.

Good recursive functions are designed to handle all valid base cases safely.

---

Rule of Thumb

Whenever you write a recursive algorithm that works on lists, ask yourself:

Is an empty list already solved?

If the answer is yes, your base case should usually be:

if len(arr) <= 1:
    return

instead of:

if len(arr) == 1:
    return

---

Key Takeaway

Many beginners think Merge Sort only needs to stop when one element remains.

In reality, it should also stop for an empty list.

Remember:

• A recursive function must have a base case.
• A list with one element is already sorted.
• An empty list is also already sorted.
• Using len(arr) <= 1 safely handles both situations.
• Using len(arr) == 1 can allow infinite recursion when an empty list is encountered.

Understanding why the base case uses <= 1 instead of == 1 is an important step toward mastering recursion and recursive sorting algorithms such as Merge Sort.

[Author]

Posts