Insertion Sort in DSA (PHP) – Complete Guide

📌 What is Insertion Sort?

Insertion Sort ek simple sorting algorithm hai jo cards arrange karne jaisa kaam karta hai 🃏

👉 Hum ek-ek element uthate hain aur usko correct position par insert kar dete hain sorted part me.

⚙️ How Insertion Sort Works

Step-by-step:

1. First element ko sorted maan lo
2. Next element uthao
3. Usko previous elements se compare karo
4. Correct position par insert karo
5. Process repeat karo

📊 Example (Dry Run)

Array:
[5, 3, 4, 1, 2]

Pass 1:

• 3 ko 5 se compare → insert before
  ➡️ [3, 5, 4, 1, 2]

Pass 2:

• 4 ko correct position par insert
  ➡️ [3, 4, 5, 1, 2]

Pass 3:

• 1 sabse aage
  ➡️ [1, 3, 4, 5, 2]

Pass 4:

• 2 correct position par
  ➡️ [1, 2, 3, 4, 5]

💻 Insertion Sort in PHP (Code Example)

<?php
function insertionSort($arr) {
    $n = count($arr);    for ($i = 1; $i < $n; $i++) {
        $key = $arr[$i];
        $j = $i - 1;        // Move elements greater than key
        while ($j >= 0 && $arr[$j] > $key) {
            $arr[$j + 1] = $arr[$j];
            $j--;
        }        $arr[$j + 1] = $key;
    }    return $arr;
}// Example
$array = [5, 3, 4, 1, 2];
$sortedArray = insertionSort($array);
print_r($sortedArray);?>

<?php
function insertionSort($arr) {
    $n = count($arr);    for ($i = 1; $i < $n; $i++) {
        $key = $arr[$i];
        $j = $i - 1;        // Move elements greater than key
        while ($j >= 0 && $arr[$j] > $key) {
            $arr[$j + 1] = $arr[$j];
            $j--;
        }        $arr[$j + 1] = $key;
    }    return $arr;
}// Example
$array = [5, 3, 4, 1, 2];
$sortedArray = insertionSort($array);
print_r($sortedArray);?>

⚡ Key Insight

👉 Insertion Sort me array gradually sorted hota hai (left side sorted part banta hai)

⏱️ Time & Space Complexity

Space Complexity:
👉 O(1) (in-place)

👍 Advantages

• Simple & intuitive
• Efficient for small datasets
• Best for almost sorted arrays
• Stable sorting algorithm

👎 Disadvantages

• Large datasets ke liye slow
• O(n²) worst case
• Comparisons zyada ho sakte hain

🎯 When to Use Insertion Sort?

• Small data sets
• Nearly sorted arrays
• Real-time data sorting
• Online sorting (data aata rahe tab bhi use ho sakta hai)

🔥 Insertion Sort vs Selection vs Bubble

🚀 Conclusion

Insertion Sort ek powerful aur simple algorithm hai jo especially nearly sorted data ke liye best perform karta hai. Beginners ke liye ye DSA ka strong foundation banata hai.