Insertion Sort

Insertion Sort is a simple sorting technique that works the way we sort playing cards in our hands:

• We take one card at a time and insert it into the correct position among the cards already sorted.

In computer terms:

• We divide the array into two parts: sorted and unsorted.

• We pick elements from the unsorted part and insert them into the correct position in the sorted part.

---

📋 Insertion Sort Algorithm

Algorithm:

1. Start from the second element (index 1), because a single element (index 0) is trivially sorted.

2. Store the current element in a variable (key). 

3. Compare the key with elements before it (to its left). 

4. Shift elements that are greater than the key to one position ahead. 

5. Insert the key at the correct position. 

6. Repeat steps 2-5 for all elements till the array is fully sorted.

---

🔥 Example:

Suppose the array is:
arr = [5, 3, 8, 6, 2]

Step-by-step:

Iteration	Action	Array State
Start	Initial array	[5, 3, 8, 6, 2]
i = 1	key = 3; 5 > 3 ⇒ shift 5 to the right	[5, 5, 8, 6, 2]
	Insert 3 at position 0	[3, 5, 8, 6, 2]
i = 2	key = 8; 8 > 5 ⇒ no shift	[3, 5, 8, 6, 2]
i = 3	key = 6; 8 > 6 ⇒ shift 8 to the right	[3, 5, 8, 8, 2]
	6 > 5 ⇒ insert 6 at position 2	[3, 5, 6, 8, 2]
i = 4	key = 2; 8 > 2 ⇒ shift 8, 6 > 2 ⇒ shift 6, 5 > 2 ⇒ shift 5, 3 > 2 ⇒ shift 3
	Insert 2 at position 0	[2, 3, 5, 6, 8]

✅ Now, the array is sorted!

---

Insertion Sort Pseudocode

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

---

✍️ Summary:

• Best case time complexity: O(n) (already sorted array)

• Average/Worst case time complexity: O(n²)

• Space complexity: O(1) (in-place)

• Stable: Yes

• Simple: Good for small datasets

✍️ C Program Insertion Sort:

#include <stdio.h>

// Function to perform  Insertion Sort

void insertionSort(int arr[], int n) {

   int i,j,key;

    for(i = 1; i < n; i++) {

        key = arr[i];

        j = i - 1;

        // Move elements greater than key one position ahead

        while(j >= 0 && arr[j] > key) {

            arr[j + 1] = arr[j];

            j--;

        }

        arr[j + 1] = key;

    }

}

void printArray(int arr[], int n) {

    for (int i=0; i<n; i++)

        printf("%d ", arr[i]);

    printf("\n");

}

void readArray(int arr[], int n) {

    for (int i=0; i<n; i++)

        scanf("%d", &arr[i]);

    

}

int main() {

    int arr[50] ;

    int n;

    

    printf("Enter the number of elements \n");

    scanf("%d",&n);

    printf("Enter the array elements\n");

    readArray(arr,n);

    

    printf("Original array: ");

    printArray(arr, n);

    insertionSort(arr, n);

    printf("Sorted array: ");

    printArray(arr, n);

    return 0;

}

Output

Enter the number of elements 

5

Enter the array elements

8 5 1 2 9

Original array: 8 5 1 2 9 

Sorted array: 1 2 5 8 9