DSA Insertion Sort

Insertion Sort is one of the simplest and most intuitive sorting algorithms.
It works the same way you might sort playing cards in your hand — picking up one card at a time and placing it in its correct position among the already sorted ones.

---

🔹 Concept Overview

The idea behind Insertion Sort is to divide the array into two parts:

• A sorted portion (on the left)
• An unsorted portion (on the right)

At each step, the algorithm takes one element from the unsorted section and inserts it into its correct position in the sorted section.

🧠 How It Works (Step-by-Step)

1. Start with the first element — it’s already “sorted” by default.
2. Take the next element from the unsorted part.
3. Compare it with elements in the sorted part and find the correct position.
4. Insert it there.
5. Repeat until every element is placed correctly.

By the end, the entire array is sorted.

---

🔹 Manual Walkthrough

Let’s manually trace how Insertion Sort works for this array:

[ 7, 12, 9, 11, 3 ]

Step 1: The first element (7) is already sorted.

[ 7 | 12, 9, 11, 3 ]

Step 2: Insert 12 into the sorted part. It’s already greater than 7 → stays in place.

[ 7, 12 | 9, 11, 3 ]

Step 3: Take 9 → place it between 7 and 12.

[ 7, 9, 12 | 11, 3 ]

Step 4: Take 11 → insert it between 9 and 12.

[ 7, 9, 11, 12 | 3 ]

Step 5: Take 3 → move it to the front.

[ 3, 7, 9, 11, 12 ]

✅ Array Sorted!

---

🔹 Algorithm Logic (Pseudocode)

for i from 1 to n-1:
    key = array[i]
    j = i - 1
    while j >= 0 and array[j] > key:
        array[j + 1] = array[j]
        j = j - 1
    array[j + 1] = key

---

🔹 Python Implementation

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]  # shift value
        j -= 1
    my_array[j + 1] = current_value   # insert in correct position

print("Sorted array:", my_array)

💡 Output:

Sorted array: [5, 11, 12, 22, 25, 34, 64, 90]

---

🔹 Visualizing the Process

Each iteration inserts one element into the sorted portion:

Initial:    [64, 34, 25, 12]
Iteration1: [34, 64, 25, 12]
Iteration2: [25, 34, 64, 12]
Iteration3: [12, 25, 34, 64]

You can think of it as gradually sliding smaller values leftward until each one finds its correct position.

---

⚙️ Improved Implementation

The simple version above shifts elements one by one.
We can make it more efficient by minimizing unnecessary swaps and breaking early when the right position is found.

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]
    position = i

    for j in range(i - 1, -1, -1):
        if my_array[j] > current_value:
            my_array[j + 1] = my_array[j]
            position = j
        else:
            break
    my_array[position] = current_value

print("Optimized Insertion Sort:", my_array)

✅ This approach avoids unnecessary shifts and exits the loop early when the correct position is found.

---

🔹 Time Complexity Analysis

Case	Description	Time Complexity
Best Case	Already sorted array	O(n)
Average Case	Random order	O(n²)
Worst Case	Reversed array	O(n²)

Even though the worst case is O(n²), Insertion Sort performs very well on small or nearly sorted datasets, which is why it’s often used in hybrid sorting algorithms (like Python’s built-in Timsort).

---

🔹 Space Complexity

• Uses only a few extra variables.
• Space Complexity: O(1) → In-place sorting.

---

🔹 When to Use Insertion Sort

✅ Ideal for:

• Small arrays
• Nearly sorted data
• Real-time applications where data arrives gradually

🚫 Not ideal for:

• Large unsorted datasets (use Merge Sort or Quick Sort instead)

---

💡 Summary

Feature	Description
Algorithm Type	Comparison-based, In-place
Stability	Stable (keeps equal elements in order)
Best Case	O(n)
Worst Case	O(n²)
Space Complexity	O(1)

---