Understanding Why Insertion Sort Uses L[j + 1] = key

[Rajeev Bagra]

Insertion Sort is one of those algorithms that seems simple at first, but a small detail can be confusing:

Why do we insert the key at j + 1 instead of j?

Let’s break it down with an example.

Example List

L = [3, 5, 7, 4]

When processing the element 4:

key = 4
j = 2

Current situation:

Index:  0  1  2  3
Value:  3  5  7  4
              j key

Step 1: Compare with 7

Since:

4 < 7

shift 7 one position to the right:

L[3] = L[2]

Result:

Index:  0  1  2  3
Value:  3  5  7  7

Move left:

j = 1

Step 2: Compare with 5

Since:

4 < 5

shift 5 one position to the right:

L[2] = L[1]

Result:

Index:  0  1  2  3
Value:  3  5  5  7

Move left:

j = 0

Step 3: Compare with 3

Now:

4 < 3

is False.

The loop stops.

Current state:

Index:  0  1  2  3
Value:  3  5  5  7
         j

Notice something important:

• j points to the value 3.
• 3 should stay to the left of 4.
• Therefore, 4 should be inserted immediately after index 0.

That position is:

j + 1

So:

L[j + 1] = key

becomes:

L[1] = 4

Result:

Index:  0  1  2  3
Value:  3  4  5  7

What If j Becomes -1?

Consider:

L = [2, 1]

Initial values:

key = 1
j = 0

Since:

1 < 2

we shift:

L[1] = L[0]

Result:

[2, 2]

and:

j = -1

The loop stops.

Now j = -1 means:

We reached the beginning of the list without finding any element smaller than or equal to the key.

Therefore the insertion position is:

j + 1 = -1 + 1 = 0

So:

L[0] = 1

Result:

[1, 2]

Key Insight

When the while loop ends:

• j points to the last element that should remain to the left of key.
• Therefore the correct insertion position is always one place to the right of j.

Visual representation:

[ elements <= key ]  j  [ elements > key ]
                         ^
                    insert key here

That is why the final statement in Insertion Sort is:

L[j + 1] = key

and not:

L[j] = key

or

L[j - 1] = key

Correct Insertion Sort Code

def insertionsort(L):
    for i in range(1, len(L)):
        key = L[i]
        j = i - 1

        while j >= 0 and key < L[j]:
            L[j + 1] = L[j]
            j = j - 1

        L[j + 1] = key

    return L

Understanding why j + 1 is used is one of the most important concepts in mastering the Insertion Sort algorithm.

[Author]

Posts