# Insertion Sort in C Language

**Insertion sort** is a *simple sorting algorithm *that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as *quicksort, heapsort, or merge sort*, but it is very efficient for small lists or partially sorted lists. In C language, an implementation of the insertion sort algorithm can be as follows:

```
#include <stdio.h>
void insertionSort(int arr[], int n) {
int i, key, j;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
/* Move elements of arr[0..i-1], that are greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
int main() {
int arr[] = { 12, 11, 13, 5, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, n);
printf("Sorted array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
```

The

function takes an integer array **insertionSort**

and its length **arr**

as arguments. It iterates over the array from the second element to the last element. For each element, it compares it with the previous elements and moves the larger elements from one position to the right until it finds the correct position for the current element. Finally, it inserts the current element into its correct position.**n**

The

function creates an integer array and calls the **main**

function to sort it. Finally, it prints the sorted array to the console.**insertionSort**

Note that the worst-case time complexity of insertion sort is **O(n^2)**, and it is not very efficient for large arrays. However, it has a small overhead and can be very efficient for small or partially sorted arrays.