In this tutorial, we will learn and write a C program to implement insertion sort. Before that you may go through the following topics in C:

**Insertion Sort Algorithm**

Insertion sort is a simple sorting algorithm that sorts the elements in an array by comparing the values at index with all its prior elements. This process takes **more time** so it is only used for small data set.

This sorting takes the first index element and compares it to its largest value in an array and it moves the element to its right location.

**C Program to implement Insertion sort**

**Question:** Insertion sort program in C using function.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | // implementation of insertion sort in C program #include <stdio.h> void insertionSort(int arr[], int n) { int i, j, key; for (i = 1; i < n; i++) { key = arr[i]; j = i - 1; //moving the value while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = key; } } int main() { int arr[30], n, i; printf("Enter the number of elements: "); scanf("%d", &n); printf("Enter %d Elements:\n", n); for (i = 0; i < n; i++) scanf("%d", &arr[i]); //calling sorting function insertionSort(arr, n); //Display the result printf("\nArray after sorting: \n"); for (i = 0; i < n; i++) printf("%d ", arr[i]); return 0; } |

**Output:**

`Enter the number of elements: 6`

Enter 6 Elements:

55

14

77

2

115

99

Array after sorting:

2 14 55 77 99 115

## Time Complexity of Heap Sort:

**Best case:**`0(n)`

**Average case:**`0(n^2)`

**Worst case:**`0(n^2)`