Follow

Follow

# Insertion Sort

Ashok
·Jan 15, 2020·

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