# Insertion Sort

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.





![Insertion-sort-example-300px.gif](https://cdn.hashnode.com/res/hashnode/image/upload/v1659081133443/En2KSAjBs.gif align="left")

Source : By Swfung8 - Own work, CC BY-SA 3.0, [https://commons.wikimedia.org/w/index.php?curid=14961606](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;
}
```