Insertion Sorting with C-Sharp Example

Back to: Data Structure Tutorial

Insertion sort is a simple sorting algorithm that works by iterating through an array and inserting each element into its correct position in a sorted subarray.

Here’s an example implementation of insertion sort in C#:

public static void InsertionSort(int[] arr)
{
    for (int i = 1; i < arr.Length; i++)
    {
        int key = arr[i];
        int j = i - 1;

        // Shift elements greater than the key to the right
        while (j >= 0 && arr[j] > key)
        {
            arr[j + 1] = arr[j];
            j--;
        }

        // Insert the key into its correct position
        arr[j + 1] = key;
    }
}

In this implementation, we start by iterating through the array from index 1 to index n-1, where n is the length of the array. We assume that the first element of the array is already sorted. For each subsequent element, we store it in a temporary variable key and compare it with the previous elements in the sorted subarray. We shift any elements greater than the key to the right by one position to make room for the key, and then insert the key into its correct position in the sorted subarray.

The time complexity of insertion sort is O(n^2) in the worst case, but it performs well on small arrays and partially sorted arrays. The algorithm is also stable, meaning that elements with the same value retain their relative order after sorting.