Why Do We Insert key at j + 1 in Insertion Sort?

[Rajeev Bagra]

The Big Idea

When learning Insertion Sort, a common question is:

If j is initially set to i - 1, then when we place key at j + 1, aren’t we just placing it back at position i?

The answer is:

Not necessarily, because j changes during the while loop.

---

The Basic Structure

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

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

    L[j + 1] = key

At the beginning:

j = i - 1

But inside the loop:

j = j - 1

moves j further and further to the left.

Therefore, by the time we execute:

L[j + 1] = key

the value of j may be very different from its original value.

---

Example 1: Key Must Move Left

Suppose:

L = [5, 2, 4]

For:

i = 1

we have:

key = 2
j = 0

Compare:

L[0] > key
5 > 2

True.

Shift:

[5, 5, 4]

Decrease j:

j = -1

Now the loop stops.

Insert the key:

L[j + 1] = L[0] = 2

Result:

[2, 5, 4]

Notice:

• Original position of key = 1
• New position of key = 0

Therefore:

j + 1 ≠ i

---

Example 2: Key Already in Correct Position

Suppose:

L = [2, 5, 7]

For:

i = 2
key = 7
j = 1

Check:

5 > 7

False.

The loop never runs.

Therefore:

j = 1

still.

Insert:

L[j + 1] = L[2] = 7

Here:

j + 1 = i

because no shifting was required.

---

What Does j Represent?

After the while loop finishes:

j

points to the last element that is less than or equal to key.

So:

j + 1

is the exact position where key should be inserted.

Think of the array like this:

[ smaller values ] [ empty slot ] [ larger values ]
                   ^
                   j + 1

The larger values have already been shifted one step to the right, creating an empty slot for key.

---

Key Insight

During Insertion Sort:

• key stays the same.
• j moves left.
• Elements larger than key are shifted right.
• The correct insertion position becomes j + 1.

Therefore, we write:

L[j + 1] = key

instead of:

L[j] = key

because j has already moved one position too far to the left.

---

Takeaway

The statement:

j = i - 1

is only true at the start of the pass.

As the algorithm runs:

j = j - 1

changes the value of j.

Therefore:

L[j + 1] = key

places the key in its correct sorted position, which may or may not be the original position i.

[Author]

Posts