# C program to implement Insertion Sort Algorithm

Insertion Sort Algorithm implementation using C program: Here, we are going to learn about the Insertion Sort Algorithm, how it works and its C language implementation.
Submitted by Sneha Dujaniya, on May 09, 2020

Insertion sort is a simple sorting algorithm that is online, stable, and in-place.

1. A stable sorting algorithm is the one where two keys having equal values appear in the same order in the sorted output array as it is present in the input unsorted array.
2. An in-place sorting algorithm has various definitions but a more used one is –
"An in-place sorting algorithm does not need extra space and uses the constant memory for manipulation of the input in-place. Although, it may require some extra constant space allowed for variables."

The basic principle followed in Insertion sort is that the key element is placed at its position in the sorted array in every iteration.

Pseudo code:

```    for i = 1 to n
key = arr[i]
j = i-1
while  j >= 0 and key < arr[j]
arr[j + 1] = arr[j]
j = j – 1
end while

arr[ j + 1 ] = key
end for
```

Example:

```    Array = 12, 14, 11, 5, 6
Initially,
we run the loop from index = 1 (14) till index = 4 (last value)

For i = 1,
compare 14 with 12 and we see, 12< 14, so no change.

For i = 2,
compare 11 with 14, and we see, 11<14,
shift 14 to next place.
Now, compare 11 with 12, we see that 11<12,
shift 12 by one place.
Now, put 11 at index 0.
Array: 11, 12, 14, 5, 6

For i = 3,
compare 5 and keep shifting the values.
Array: 5, 11, 12, 14, 6

For i = 4,
compare with all the previous elements and
keep shifting the values accordingly.
```

Time Complexity: The time complexity of Insertion Sort can be described as: T(n) = T(n/2) + C

• Worst case: O(n^2)
• Average Case: O(n^2)
• Best case: O(n), when the array is already sorted
• Space Complexity: O(1)

C Implementation:

```#include <stdio.h>

void insertion(int arr[], int n)
{
int i, j;
for (i = 1; i < n; i++) {
int key = arr[i];
j = i - 1;
while (key < arr[j] && j >= 0) {
arr[j + 1] = arr[j];
j--;
}

arr[j + 1] = key;
}
printf("\nAfter performing Insertion sort:\n");
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
}

int main()
{

int arr[] = { 10, 14, 3, 8, 5, 12, 16, 13 };
int n = sizeof(arr) / sizeof(arr);

insertion(arr, n);

return 0;
}
```

Output

```After performing Insertion sort:
3 5 8 10 12 13 14 16
```

Insertion Sort can be optimized using Binary Insertion sorting. We must use Insertion sort where the elements are mostly sorted and only some elements are misplaced. Also, it should be used where there is lesser number of data points due to its large time complexity.