Insertion Sort Algorithm and In-Place Analysis

Insertion Sort ek practical aur intuitive sorting algorithm hai jo bilkul waise kaam karta hai jaise hum apne haath me taash (playing cards) ko sort karte hain. Hum ek ek naya card uthate hain aur use already sorted cards ke beech uski sahi position par insert karte hain.

Working Principle

Index 1 se start karke har element ko hum key maante hain. Key se pehle ke elements already sorted order me hote hain. Agar sorted portion ke elements key se bade hain, toh unhe ek step right shift karte hain jab tak key ke liye sahi spot na mil jaye.

Initial Array: [ 12, 11, 13, 5, 6 ]

Pass 1 (key = 11, index 1):
Compare with 12: 12 > 11 -> Shift 12 right -> [ _ , 12, 13, 5, 6 ]
Insert key 11:   [ 11, 12, 13, 5, 6 ]

Pass 2 (key = 13, index 2):
Compare with 12: 12 < 13 -> No shift needed
Array:           [ 11, 12, 13, 5, 6 ]

Pass 3 (key = 5, index 3):
Shift 13, 12, 11 right -> [ _ , 11, 12, 13, 6 ]
Insert key 5:    [ 5, 11, 12, 13, 6 ]

Pass 4 (key = 6, index 4):
Shift 13, 12, 11 right -> [ 5, _ , 11, 12, 13 ]
Insert key 6:    [ 5, 6, 11, 12, 13 ] -> Sorted!

Insertion Sort Algorithm

INSERTION_SORT(A, N)
1. For i = 1 to N - 1 do:
2.     Set key = A[i]
3.     Set j = i - 1
4.     While j >= 0 and A[j] > key do:
5.         A[j + 1] = A[j]    [Shift right]
6.         j = j - 1
7.     End While
8.     A[j + 1] = key         [Place key]
9. End For

Complexity and Key Benefits

• Best-case Time: O(n) – Jab array already sorted ho (inner while loop har bar 1 check karke fail ho jata hai).
• Worst-case Time: O(n^2) – Jab array reverse sorted ho (maximum shifts).
• Space Complexity: O(1) auxiliary space (In-place).
• Stability: Stable sorting algorithm.
• Adaptive: Agar data nearly-sorted hai, toh insertion sort bohot tez perform karta hai. Practical systems me hybrid sorting algorithms (jaise Timsort) small subarrays (size < 32) ke liye insertion sort hi use karte hain.

Agli post me hum cover karenge Merge Sort Algorithm (Divide and Conquer Approach).