# Insertion Sort in C Language

142Views

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);

insertionSort(arr, n);

printf("Sorted array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}

return 0;
}
``````

The `insertionSort` function takes an integer array `arr` and its length `n` 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.

The `main` function creates an integer array and calls the `insertionSort` function to sort it. Finally, it prints the sorted array to the console.

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. Copyright notice: Our original article, by Amitesh Kumar 2023-02-22 publish, total 1356 words.