# 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.

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;
}
```