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 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.