Insertion sort is a simple , adaptive , stable , Inplace sorting algorithm.

Insertion sort is an online algorithm i.e. insertion sort can sort its input piece by piece in a serial fashion.

Insertion sort performs two operations: It scans through the list, comparing each pair of elements, and it shifts the elements if they are out of order. In a sense, it's similar to sorting playing cards.

Source : By Swfung8 - Own work, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=14961606

Time complexity

Worst case performance : O(n^2) , when we want to sort a list in ascending order, but it is arranged in descending order.

Average case performance : O(n^2) , When the list is in random order.

Best Case performance : O(n) , When the list is already in sorted order.

Insertion Sort in C#

static int[] InsertionSort(int[] input)
{
    int j, currentvalue;
    for (int i = 1; i < input.Length; i++)
    {
        currentvalue = input[i];
        j = i - 1;
        while (j >= 0 && (input[j] > currentvalue))
        {
            input[j + 1] = input[j];
            j--;
        }
        input[j + 1] = currentvalue;

    }
    return input;
}