C program to implement insertion sort algorithm

Insertion sort algorithm implementation in C: In this tutorial, we will learn about the insertion sort algorithm, pseudo code, example, time complexity, and how to implement insertion sort algorithm using the C program? By Sneha Dujaniya Last updated : August 03, 2023

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

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.
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 program to implement insertion sort algorithm

#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[0]);

    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.