- This topic is empty.
-
Posts
-
When learning Insertion Sort, a common question is:
«If the algorithm uses “L[j + 1]”, doesn’t that create a new position in the list and increase its size?»
The answer is No.
Let’s see why.
The Key Idea
In Insertion Sort, statements such as:
L[j + 1] = L[j]
do not create a new element.
They simply replace the value already stored at that index.
The size of the list remains exactly the same throughout the entire algorithm.
An Example
Suppose we have:
L = [2, 4, 5, 6, 3]
The length of the list is:
len(L) = 5
Indexes:
Index: 0 1 2 3 4
Value: 2 4 5 6 3
Step 1: Save the Key
Before any shifting begins, Insertion Sort stores the key in a temporary variable:
key = L[i]
So:
key = 3
Now the value “3” is safely stored outside the array.
Think of it as:
Array: [2, 4, 5, 6, _]
Key : 3
Step 2: Shift Elements Right
Initially:
j = 3
The algorithm checks:
L[j] > key
which becomes:
6 > 3
True.
So:
L[j + 1] = L[j]
becomes:
L[4] = L[3]
Result:
Before:
[2, 4, 5, 6, 3]After:
[2, 4, 5, 6, 6]Notice carefully:
- No new position was created.
- The value at index 4 was simply overwritten.
- The list still contains 5 elements.
Step 3: Continue Shifting
Next:
j = 2
The algorithm executes:
L[3] = L[2]
Result:
Before:
[2, 4, 5, 6, 6]After:
[2, 4, 5, 5, 6]Again:
- No new element is added.
- An existing value is replaced.
- Length remains 5.
The “Moving Hole” Visualization
Many textbooks explain Insertion Sort using a “hole”.
Imagine removing the key from the array:
[2, 4, 5, 6, _]
Now shift larger elements right:
[2, 4, 5, _, 6]
[2, 4, _, 5, 6]
[2, _, 4, 5, 6]
Finally place the key into the hole:
[2, 3, 4, 5, 6]
At every stage there are still exactly 5 positions.
Nothing was added.
What Actually Increases a List’s Size?
Operations like:
L.append(10)
or
L.insert(2, 10)
create new elements.
Example:
L = [2, 4, 5]
After:
L.append(10)
we get:
[2, 4, 5, 10]
The length changes from 3 to 4.
Insertion Sort never performs such operations.
The Big Takeaway
The statement:
L[j + 1] = …
does not mean:
«”Create a new element at position j + 1.”»
Instead it means:
«”Replace the value already stored at position j + 1.”»
That is why Insertion Sort can rearrange elements while keeping the length of the list exactly the same from start to finish.
- You must be logged in to reply to this topic.