C# Program for Insertion Sort with Example and Explanation

You can perform insertion sort in C# by looping through the array and inserting each element into its correct position using nested for loops; for example, 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; } sorts the array in place.

Examples

Input[5, 2, 9, 1]

Output[1, 2, 5, 9]

Input[3, 3, 2, 1]

Output[1, 2, 3, 3]

Input[]

Output[]

How to Think About It

To sort an array using insertion sort, think of dividing the array into a sorted part and an unsorted part. Start from the second element and compare it with elements before it. Move elements that are bigger one step to the right to make space, then insert the current element in the correct position. Repeat this for all elements until the whole array is sorted.

Algorithm

1

Start from the second element of the array (index 1).

2

Store the current element as the key.

3

Compare the key with elements before it in the sorted part.

4

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

5

Insert the key into the correct position.

6

Repeat for all elements until the array is sorted.

Code

csharp

using System;
class Program {
    static void InsertionSort(int[] arr) {
        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;
        }
    }
    static void Main() {
        int[] numbers = {5, 2, 9, 1};
        InsertionSort(numbers);
        Console.WriteLine(string.Join(", ", numbers));
    }
}

Output

1, 2, 5, 9

Dry Run

Let's trace the array [5, 2, 9, 1] through the insertion sort code.

1

Start with i=1, key=2

Compare 2 with 5; since 5 > 2, shift 5 right. Insert 2 at position 0. Array becomes [2, 5, 9, 1].

2

i=2, key=9

Compare 9 with 5; 5 < 9, no shift needed. Insert 9 at position 2. Array stays [2, 5, 9, 1].

3

i=3, key=1

Compare 1 with 9, 5, 2; all are greater, shift them right. Insert 1 at position 0. Array becomes [1, 2, 5, 9].

Iteration	Array State
Start	[5, 2, 9, 1]
i=1	[2, 5, 9, 1]
i=2	[2, 5, 9, 1]
i=3	[1, 2, 5, 9]

Why This Works

Step 1: Choosing the key

The element at index i is chosen as the key to insert into the sorted part of the array.

Step 2: Shifting elements

Elements greater than the key are moved one position to the right to make space for the key.

Step 3: Inserting the key

The key is placed in the correct position so the sorted part remains ordered.

Alternative Approaches

Using List and Insert

csharp

using System;
using System.Collections.Generic;
class Program {
    static void InsertionSort(List<int> list) {
        for (int i = 1; i < list.Count; i++) {
            int key = list[i];
            int j = i - 1;
            while (j >= 0 && list[j] > key) {
                list[j + 1] = list[j];
                j--;
            }
            list[j + 1] = key;
        }
    }
    static void Main() {
        var numbers = new List<int>{5, 2, 9, 1};
        InsertionSort(numbers);
        Console.WriteLine(string.Join(", ", numbers));
    }
}

This uses a List<int> instead of an array, which allows dynamic resizing but has similar performance.

Recursive Insertion Sort

csharp

using System;
class Program {
    static void RecursiveInsertionSort(int[] arr, int n) {
        if (n <= 1) return;
        RecursiveInsertionSort(arr, n - 1);
        int last = arr[n - 1];
        int j = n - 2;
        while (j >= 0 && arr[j] > last) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = last;
    }
    static void Main() {
        int[] numbers = {5, 2, 9, 1};
        RecursiveInsertionSort(numbers, numbers.Length);
        Console.WriteLine(string.Join(", ", numbers));
    }
}

This approach uses recursion to sort the array, which can be less efficient and harder to read for beginners.

Complexity: O(n^2) time, O(1) space

Time Complexity

Insertion sort uses nested loops: the outer loop runs n times, and the inner loop can run up to n times in the worst case, resulting in O(n^2) time.

Space Complexity

It sorts the array in place without extra arrays, so space complexity is O(1).

Which Approach is Fastest?

The iterative insertion sort is simple and efficient for small or nearly sorted data; recursive version adds overhead and is slower.

Approach	Time	Space	Best For
Iterative Insertion Sort	O(n^2)	O(1)	Small or nearly sorted arrays
Recursive Insertion Sort	O(n^2)	O(n) due to recursion stack	Educational or recursive practice
List-based Insertion Sort	O(n^2)	O(1)	When using dynamic lists instead of arrays