DSA Insertion Sort

DSA Insertion Sort

Insertion Sort is one of the most intuitive sorting algorithms.
It works the same way we sort cards in our hand—by taking one card at a time and inserting it into the correct position.

What is Insertion Sort?

The Insertion Sort algorithm:

Uses two parts of the array
- Sorted part (left side)
- Unsorted part (right side)
Takes one value at a time from the unsorted part
Inserts it into the correct position in the sorted part
Repeats until the array is fully sorted

The first element is always considered already sorted.

Speed (In Simple Words)

Fast for small arrays
Very efficient for nearly sorted data
Slow for large, random arrays

How Insertion Sort Works (Step Logic)

Take the first value → consider it sorted
Pick the next value from the unsorted part
Compare it with values in the sorted part
Shift larger values one position to the right
Insert the value at the correct position
Repeat for all remaining values

Manual Run-Through (Step by Step)

Initial Array

Step 1: First element is sorted

Step 2: Insert 12

12 > 7 → already in correct place

Step 3: Insert 9

Move 9 between 7 and 12

Step 4: Insert 11

Move 11 between 9 and 12

Step 5: Insert 3

3 is smallest → move to front

Final Sorted Array

What Happened in the Manual Run?

✔ First element assumed sorted
✔ Each new element compared only with sorted part
✔ Sorted part grows from left to right
✔ Unsorted part shrinks each pass
✔ Total passes = n − 1 (for n elements)

Insertion Sort Algorithm (Conceptual)

Outer loop → selects next element to insert
Inner loop → finds correct position in sorted part
Elements larger than the key are shifted, not swapped

Basic Insertion Sort (Simple Logic – Python Style)

my_array = [64, 34, 25, 12, 22, 11, 90, 5]

n = len(my_array)
for i in range(1, n):
insert_index = i
current_value = my_array.pop(i)
for j in range(i - 1, -1, -1):
if my_array[j] > current_value:
insert_index = j
my_array.insert(insert_index, current_value)

print("Sorted array:", my_array)

my_array = [64, 34, 25, 12, 22, 11, 90, 5]

n = len(my_array)

for i in range(1, n):

insert_index = i

current_value = my_array.pop(i)

for j in range(i - 1, -1, -1):

if my_array[j] > current_value:

insert_index = j

my_array.insert(insert_index, current_value)

print("Sorted array:", my_array)

Easy to understand but internally expensive due to hidden memory shifts.

Why This Can Be Slow (Important Concept)

In high-level languages (Python, JS):

remove → shifts many elements left
insert → shifts many elements right
These hidden memory shifts cost time

You don’t see them, but the computer still does the work.

Optimized Insertion Sort (Efficient Version)

Instead of removing and inserting:

Store the value
Shift only required elements
Insert once

my_array = [64, 34, 25, 12, 22, 11, 90, 5]

n = len(my_array)
for i in range(1, n):
current_value = my_array[i]
j = i - 1

while j >= 0 and my_array[j] > current_value:
my_array[j + 1] = my_array[j]
j -= 1

my_array[j + 1] = current_value

print("Sorted array:", my_array)

my_array = [64, 34, 25, 12, 22, 11, 90, 5]

n = len(my_array)

for i in range(1, n):

current_value = my_array[i]

j = i - 1

while j >= 0 and my_array[j] > current_value:

my_array[j + 1] = my_array[j]

j -= 1

my_array[j + 1] = current_value

print("Sorted array:", my_array)

Why This Is Better

✔ Fewer memory shifts
✔ Breaks early when correct position is found
✔ Used in real implementations

Insertion Sort Time Complexity

Insertion Sort works on n elements.

Comparisons

On average, each element compares with about n/2 elements
Loop runs approximately n times

Final Complexity

⏱ Time Complexity Table

Case	Condition	Time Complexity
Best Case	Already sorted	O(n)
Average Case	Random order	O(n²)
Worst Case	Reverse sorted	O(n²)

📌 Best case is fast because no shifting is required.

Space Complexity

Metric	Value
Extra Space	O(1)
Type	In-place

Key Properties (Exam Gold)

✔ Stable sorting algorithm
✔ Adaptive (responds to existing order)
✔ In-place
✔ Efficient for small / nearly sorted arrays
❌ Not suitable for large datasets

✅ Final Summary

✔ Insertion Sort builds a sorted array gradually
✔ Works like sorting playing cards
✔ Very intuitive and easy to implement
✔ Optimized version reduces memory shifts
✔ Best case: O(n)
✔ Worst case: O(n²)
✔ Excellent for learning and interviews

DSA Insertion Sort