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 cards already held.

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

Sorted portion ↑
[5] [3, 8, 6, 2]

After first insertion:
[3, 5] [8, 6, 2]

Pointers:
i -> current element to insert
j -> position to compare in sorted part

Dry Run Walkthrough

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

Goal: Sort the array in ascending order using insertion sort

Step 1: Start with second element (3), compare with 5 and insert before it

[3, 5, 8, 6, 2]

Why: 3 is smaller than 5, so it moves left to keep sorted order

Step 2: Take third element (8), compare with 5, stays in place

[3, 5, 8, 6, 2]

Why: 8 is greater than 5, so it stays after 5

Step 3: Take fourth element (6), compare with 8 and 5, insert between 5 and 8

[3, 5, 6, 8, 2]

Why: 6 is less than 8 but greater than 5, so it fits between them

Step 4: Take fifth element (2), compare with 8, 6, 5, 3 and insert at start

[2, 3, 5, 6, 8]

Why: 2 is smallest, so it moves to the front

Result:

[2, 3, 5, 6, 8]

Annotated Code

DSA C#

using System;

class InsertionSort {
    public static void Sort(int[] arr) {
        for (int i = 1; i < arr.Length; 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
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }

    public static void PrintArray(int[] arr) {
        for (int i = 0; i < arr.Length; i++) {
            Console.Write(arr[i]);
            if (i < arr.Length - 1) Console.Write(", ");
        }
        Console.WriteLine();
    }

    static void Main() {
        int[] arr = {5, 3, 8, 6, 2};
        Console.WriteLine("Original array:");
        PrintArray(arr);
        Sort(arr);
        Console.WriteLine("Sorted array:");
        PrintArray(arr);
    }
}

for (int i = 1; i < arr.Length; 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 for key

j--;

move left to check next element

arr[j + 1] = key;

insert key at correct sorted position

Output

Original array:

5, 3, 8, 6, 2

Sorted array:

2, 3, 5, 6, 8

Complexity Analysis

Time: O(n^2) because in worst case each element is compared 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

no operations, array remains empty

DSA C#

for (int i = 1; i < arr.Length; i++) {

array with one element

no changes needed, array stays the same

DSA C#

for (int i = 1; i < arr.Length; i++) {

array already sorted

minimal shifts, algorithm runs faster

DSA C#

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

When to Use This Pattern

When you see a problem asking to sort or partially sort a small or nearly sorted list, reach for insertion sort because it inserts elements one by one efficiently.

Common Mistakes

Mistake: Not shifting elements to the right 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, causing unnecessary comparisons
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 nearly sorted arrays where simple sorting is efficient.

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. It builds the sorted array one element at a time by inserting elements in their correct position.

B. It divides the array into halves and sorts each half recursively.

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

D. It selects the smallest element and swaps it with the first unsorted element.

Solution

1. Step 1: Understand insertion sort process

   Insertion sort takes one element at a time and inserts it into the correct position in the already sorted part of the array.

2. Step 2: Compare with other sorting methods

   Other options describe merge sort (B), bubble sort (C), and selection sort (D), which are different algorithms.

3. Final Answer:

   It builds the sorted array one element at a time by inserting elements in their 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 selection sort with insertion sort

2. Which of the following is the correct syntax to start the outer loop for insertion sort in C# for an array arr of length n?

easy

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

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

C. for (int i = n - 1; i >= 0; i--)

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

Solution

1. Step 1: Identify starting index for insertion sort

   Insertion sort starts from the second element (index 1) because the first element is considered sorted.

2. Step 2: Check loop conditions

   The loop runs while i < n to cover all elements. for (int i = 1; i < n; i++) matches this.

3. Final Answer:

   for (int i = 1; i < n; i++) -> Option D

4. Quick Check:

   Start from 1 to n-1 for insertion sort loop [OK]

Hint: Start outer loop at 1, not 0, for insertion sort [OK]

Common Mistakes:

• Starting loop at 0 instead of 1
• Using <= n instead of < n causing out-of-bounds
• Counting backwards incorrectly

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

medium

A. [1, 3, 2, 4]

B. [4, 3, 2, 1]

C. [1, 2, 3, 4]

D. [2, 3, 4, 1]

Solution

1. Step 1: Trace insertion sort on given array

   Start with 4 (sorted). Insert 3 before 4 -> [3,4,2,1]. Insert 2 before 3 -> [2,3,4,1]. Insert 1 before 2 -> [1,2,3,4].

2. Step 2: Confirm final sorted array

   The array is sorted in ascending order: [1, 2, 3, 4].

3. Final Answer:

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

4. Quick Check:

   Insertion sort sorts ascending -> [1, 2, 3, 4] [OK]

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

Common Mistakes:

• Assuming array stays unchanged
• Mixing up positions during insertion
• Stopping before fully sorting

4. Identify the error in this insertion sort code snippet:

for (int i = 1; i < arr.Length; 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 variable j should start at i - 1 instead of i + 1.

B. The while loop condition should use j < arr.Length instead of j >= 0.

C. The key should be assigned after the while loop, not before.

D. The array index arr[j + 1] causes out-of-bounds error.

Solution

1. Step 1: Check initialization of j

   In insertion sort, j starts at the element before i, so it should be i - 1, not i + 1.

2. Step 2: Verify while loop condition and shifting

   The condition j >= 0 is correct to move backwards. The shifting logic is correct if j starts properly.

3. Final Answer:

   The variable j should start at i - 1 instead of i + 1. -> Option A

4. Quick Check:

   j starts at i-1 to compare previous elements [OK]

Hint: j must start left of i to compare previous elements [OK]

Common Mistakes:

• Starting j at i+1 causing wrong comparisons
• Incorrect while loop boundary causing errors
• Misplacing key assignment inside loop

5. Given a nearly sorted array int[] arr = {1, 2, 4, 3, 5, 6}, how many element shifts will insertion sort perform to fully sort it?

hard

A. 2

B. 1

C. 3

D. 4

Solution

1. Step 1: Identify where shifts occur

   Only the element 3 is out of order. It needs to be inserted before 4.

2. Step 2: Count shifts to insert 3

   To insert 3, j=2 (arr[2]=4 > 3), shift arr[3]=arr[2] (1 shift), j=1 (arr[1]=2 < 3), stop. Place arr[2]=3 (not a shift).

3. Step 3: Check if other shifts occur

   No other elements need shifting. Total shifts = 1.

4. Final Answer:

   1 -> Option B

5. Quick Check:

   One shift when inserting 3 [OK]

Hint: Count only elements moved to insert out-of-place items [OK]

Common Mistakes:

• Counting swaps instead of shifts
• Ignoring that placing key is not a shift
• Assuming all elements shift