Insertion Sort Algorithm in DSA C

Mental Model

Insertion sort builds a sorted list one item at a time by inserting each new item into its correct place.

Analogy: Imagine sorting playing cards in your hand by picking one card at a time and placing it in the right position among the already sorted cards.

Unsorted array: [5, 3, 8, 6, 2]
Sorted portion ↑ starts empty and grows rightwards
[5, 3, 8, 6, 2]
 ↑

Dry Run Walkthrough

Input: array: [5, 3, 8, 6, 2]

Goal: Sort the array in ascending order using insertion sort

Step 1: Take element 3 and compare with 5, shift 5 right and insert 3 before it

[3, 5, 8, 6, 2]

Why: 3 is smaller than 5, so it must be placed before 5 to keep sorted order

Step 2: Take element 8, it is greater than 5, so keep it in place

[3, 5, 8, 6, 2]

Why: 8 is already in correct position relative to sorted part

Step 3: Take element 6, compare with 8 and 5, shift 8 right and insert 6 after 5

[3, 5, 6, 8, 2]

Why: 6 fits between 5 and 8, so 8 moves right to make space

Step 4: Take element 2, compare with 8, 6, 5, 3, shift all right and insert 2 at start

[2, 3, 5, 6, 8]

Why: 2 is smallest, so it moves to the front, shifting all others right

Result:

Final sorted array: [2, 3, 5, 6, 8]

Annotated Code

DSA C

#include <stdio.h>

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;

        // Move elements of arr[0..i-1], that are greater than key,
        // to one position ahead of their current position
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d", arr[i]);
        if (i < n - 1) printf(" -> ");
    }
    printf(" -> null\n");
}

int main() {
    int arr[] = {5, 3, 8, 6, 2};
    int n = sizeof(arr) / sizeof(arr[0]);

    insertionSort(arr, n);
    printArray(arr, n);

    return 0;
}

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

iterate over each element starting from second to insert it into sorted part

int key = arr[i];

store current element to insert

int j = i - 1;

start comparing with previous element in sorted part

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

shift elements greater than key one position right

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

move element right to make space

j = j - 1;

move left to compare next element

arr[j + 1] = key;

insert key in correct position

Output

2 -> 3 -> 5 -> 6 -> 8 -> null

Complexity Analysis

Time: O(n^2) because in worst case each element is compared and shifted with all previous elements

Space: O(1) because sorting is done in place without extra arrays

vs Alternative: Compared to bubble sort, insertion sort is often faster on nearly sorted data because it stops early when elements are in order

Edge Cases

empty array

function completes immediately without changes

DSA C

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

array with one element

no shifts needed, array remains same

DSA C

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

array already sorted

while loop condition fails quickly, minimal shifts

DSA C

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

When to Use This Pattern

When you need to sort small or nearly sorted lists efficiently and want a simple method, reach for insertion sort because it inserts elements into a growing sorted section.

Common Mistakes

Mistake: Not shifting elements before inserting the key, causing overwriting
Fix: Shift elements greater than key one position right before placing key

Mistake: Starting loop from index 0 instead of 1
Fix: Start from index 1 because first element is trivially sorted

Summary

Insertion sort builds a sorted array by inserting each element into its correct position.

Use it for small or mostly sorted data where simple implementation is preferred.

The key insight is shifting larger elements right to make space for the current element.

Practice

1. What is the main idea behind the Insertion Sort algorithm?

easy

A. Build the sorted array one element at a time by inserting elements in the correct position

B. Divide the array into halves and sort each half recursively

C. Swap adjacent elements if they are in the wrong order repeatedly

D. Use a heap data structure to sort elements

Solution

1. Step 1: Understand insertion sort process

   Insertion sort builds the sorted list by taking one element at a time and placing it in the correct position among the already sorted elements.

2. Step 2: Compare with other sorting methods

   Other options describe different algorithms: divide and conquer is merge sort, swapping adjacent elements is bubble sort, and heap data structure is heap sort.

3. Final Answer:

   Build the sorted array one element at a time by inserting elements in the correct position -> Option A

4. Quick Check:

   Insertion sort = Insert elements step-by-step [OK]

Hint: Insertion sort inserts elements one by one in order [OK]

Common Mistakes:

• Confusing insertion sort with bubble sort
• Thinking insertion sort divides array recursively
• Mixing up heap sort with insertion sort

2. Which of the following is the correct syntax for the inner loop in insertion sort in C?

easy

A. for (int j = n - 1; j > i; j--)

B. for (int j = 0; j < i; j++)

C. for (int j = i - 1; j >= 0 && arr[j] > key; j--)

D. for (int j = i + 1; j < n; j++)

Solution

1. Step 1: Identify inner loop role in insertion sort

   The inner loop moves backward from the current element's previous index, shifting elements greater than the key to the right.

2. Step 2: Match syntax with this logic

   for (int j = i - 1; j >= 0 && arr[j] > key; j--) correctly uses a loop starting from i-1 down to 0, checking if arr[j] > key and decrementing j.

3. Final Answer:

   for (int j = i - 1; j >= 0 && arr[j] > key; j--) -> Option C

4. Quick Check:

   Inner loop moves backward while arr[j] > key [OK]

Hint: Inner loop goes backward checking elements > key [OK]

Common Mistakes:

• Using forward loop instead of backward
• Not checking arr[j] > key condition
• Incorrect loop boundaries

3. What will be the output array after running insertion sort on int arr[] = {4, 3, 2, 1};?

medium

A. [4, 3, 2, 1]

B. [1, 3, 2, 4]

C. [2, 3, 4, 1]

D. [1, 2, 3, 4]

Solution

1. Step 1: Trace insertion sort on given array

   Start with 4, then insert 3 before 4, array becomes [3,4,2,1]. Insert 2 before 3, array becomes [2,3,4,1]. Insert 1 before 2, array becomes [1,2,3,4].

2. Step 2: Confirm final sorted array

   After all insertions, the array is sorted ascending: [1, 2, 3, 4].

3. Final Answer:

   [1, 2, 3, 4] -> Option D

4. Quick Check:

   Sorted ascending = [1, 2, 3, 4] [OK]

Hint: Insertion sort sorts ascending step-by-step [OK]

Common Mistakes:

• Assuming array stays the same
• Mixing up partial sorted arrays
• Not moving elements correctly

4. Identify the error in this insertion sort snippet:

for (int i = 1; i < n; i++) {
  int key = arr[i];
  int j = i - 1;
  while (j >= 0 && arr[j] < key) {
    arr[j + 1] = arr[j];
    j--;
  }
  arr[j + 1] = key;
}

medium

A. The loop should start from i = 0, not i = 1

B. The comparison in while loop should be arr[j] > key, not arr[j] < key

C. The assignment arr[j + 1] = key is outside the loop

D. Variable j should be incremented, not decremented

Solution

1. Step 1: Understand insertion sort comparison logic

   Insertion sort shifts elements greater than key to the right, so condition must be arr[j] > key.

2. Step 2: Check given code's while condition

   The code uses arr[j] < key, which incorrectly shifts smaller elements, breaking sorting.

3. Final Answer:

   The comparison in while loop should be arr[j] > key, not arr[j] < key -> Option B

4. Quick Check:

   Correct comparison is arr[j] > key [OK]

Hint: Shift elements greater than key, so use > in condition [OK]

Common Mistakes:

• Using < instead of > in while condition
• Starting loop from wrong index
• Misplacing key assignment

5. Given an array int arr[] = {5, 2, 9, 1, 5, 6};, how many total shifts (element moves) does insertion sort perform to sort it?

hard

A. 6

B. 9

C. 7

D. 10

Solution

1. Step 1: Trace insertion sort shifts step-by-step

   Start with array: [5,2,9,1,5,6]
   i=1 (key=2): shift 5 right (1 shift) -> [2,5,9,1,5,6]
   i=2 (key=9): no shift (0 shifts)
   i=3 (key=1): shift 9, then 5, then 2 right (3 shifts) -> [1,2,5,9,5,6]
   i=4 (key=5): shift 9 right (1 shift) -> [1,2,5,5,9,6]
   i=5 (key=6): shift 9 right (1 shift) -> [1,2,5,5,6,9]
   Total shifts = 1 + 0 + 3 + 1 + 1 = 6 shifts

2. Step 2: Confirm total shifts

   Counting carefully, total shifts are 6.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Count shifts carefully = 6 [OK]

Hint: Count each element move during insertion steps [OK]

Common Mistakes:

• Counting only key placements, not shifts
• Missing multiple shifts in one iteration
• Confusing swaps with shifts