Introduction

Insertion sort is O(n^2) in the worst case, but its best case is O(n) because the inner loop does almost no work when the array is already sorted. The key idea is that Big-O best-case analysis counts what the algorithm actually does on the easiest input, not what the nested loop structure might suggest at first glance.

How Insertion Sort Works

Insertion sort grows a sorted prefix from left to right. For each position, it takes the current value and moves it left until it reaches the correct spot.

Here is a standard implementation:

1def insertion_sort(values):
2    for i in range(1, len(values)):
3        key = values[i]
4        j = i - 1
5
6        while j >= 0 and values[j] > key:
7            values[j + 1] = values[j]
8            j -= 1
9
10        values[j + 1] = key
11
12
13data = [1, 2, 3, 4, 5]
14insertion_sort(data)
15print(data)

The while loop is where most of the work happens in difficult inputs.

What Happens in the Best Case

The best case is an array that is already sorted:

[1, 2, 3, 4, 5]

For each iteration:

• the algorithm picks key
• it checks whether the previous element is greater than key
• the condition fails immediately
• no shifting happens

So for each position, the inner loop performs only one comparison and then stops.

That means the total work is proportional to the number of elements, not the square of the number of elements.

Counting the Operations

Suppose the array has n elements. The outer loop runs n - 1 times.

In the best case:

• iteration 1 does one comparison
• iteration 2 does one comparison
• iteration 3 does one comparison
• and so on

So the total number of important comparisons is roughly n - 1, which is linear:

O(n)

There is no long chain of shifts, because every element is already in the correct position relative to the sorted prefix.

Why the Worst Case Is Different

Now compare that with a reverse-sorted array:

[5, 4, 3, 2, 1]

When insertion sort reads 4, it must shift 5. When it reads 3, it must shift both 5 and 4. When it reads 2, it must shift three elements.

That creates the familiar sum:

1 + 2 + 3 + ... + (n - 1)

which is O(n^2).

So the same algorithm has very different behavior depending on the amount of disorder in the input.

Insertion Sort Is Adaptive

This is why insertion sort is called adaptive. It runs faster on data that is already sorted or nearly sorted.

For example:

data = [1, 2, 4, 3, 5, 6]
insertion_sort(data)
print(data)

Only one small out-of-order region needs fixing, so the algorithm behaves much closer to linear time than to quadratic time.

That is also why insertion sort is often used as a base case inside more advanced algorithms for small or nearly sorted partitions.

The Nested-Loop Misconception

Beginners often see an outer loop plus an inner loop and conclude that the runtime must always be O(n^2). That is not how complexity analysis works.

You have to ask:

• how many times does the inner loop actually run
• on what inputs does it stop early

In insertion sort's best case, the inner loop does not scan backward through the sorted prefix. It exits immediately each time.

That is why the best-case complexity is linear even though the code contains a nested loop.

Common Pitfalls

The biggest mistake is counting the potential loop structure instead of the actual work done for the best-case input.

Another common mistake is forgetting that best case assumes the easiest possible valid input, which for insertion sort is an already sorted array.

Developers also sometimes mix up best case and average case. Insertion sort is O(n) only in the best case, not on arbitrary random data.

Finally, do not assume every sorting algorithm benefits equally from already sorted input. Insertion sort is adaptive, but some algorithms do not improve as dramatically.

Summary

• Insertion sort has best-case time O(n) because the inner loop stops immediately on sorted input.
• The outer loop still runs, but each pass does only constant extra work.
• Worst-case O(n^2) happens when many elements must shift left.
• The algorithm is adaptive, so nearly sorted data is handled efficiently.
• Nested loops do not automatically mean quadratic time; the actual number of inner-loop iterations matters.