Insertion Sort is a simple sorting algorithm that builds the final sorted array one element at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heap sort, or merge sort.

1. Start with the second element in the list (assuming the first element is already sorted).
2. Compare the current element with the previous elements.
3. If the current element is smaller, shift the larger elements to the right.
4. Insert the current element in the correct position in the sorted part of the array.
5. Repeat steps 1-4 for the remaining unsorted elements until the entire list is sorted.

   Insertion-Sort(A, N)
1. for j <--- 2 to N
2.     key <--- A[ j ]
3.     i =  j - 1
4.     while ( i > 0 ) and ( A[ i ] > key )
6.        A[ i + 1 ] <--- A [ i ]
7.        i = i + 1
8.     A[ i + 1 ] <--- key
9. Stop

Insertion Sort is a straightforward sorting algorithm that builds the final sorted array one element at a time. Let's explore how it works:

1. Initialization:

   • Start with the second element in the list, assuming the first element is already sorted.

2. Comparison and Insertion:

   • Compare the current element with the previous elements in the sorted part of the array.
   • If the current element is smaller, shift the larger elements to the right.
   • Insert the current element in the correct position in the sorted part of the array.

3. Repeat:

   • Repeat steps 1-2 for the remaining unsorted elements until the entire list is sorted.

#include <stdio.h>

int array[10];

void input_array(int[], int);
void print_array(int[], int);
void insertion_sort(int[], int);

void main()
{
    input_array(array, 5);
    insertion_sort(array, 5);
    print_array(array, 5);
}

void input_array(int A[], int N)
{
    int i;

    printf("\nSorted array is : {");
    for (i = 1; i <= N; i++)
    {
        if (i != N)
            printf("%d, ", A[i]);
        else
            printf("%d}", A[i]);
    }
}

void print_array(int A[], int N)
{
    int i;

    printf("\nSorted array is : {");
    for (i = 1; i <= N; i++)
    {
        printf("%d, ", A[i]);
    }
    printf("}");
}

void insertion_sort(int A[], int N)
{
    int key, i, j;

    for (j = 1; j <= N; j++)
    {
        key = A[j];
        i = j - 1;

        while (i > 0 && A[i] > key)
        {
            A[i + 1] = A[i];
            i--;
        }

        A[i + 1] = key;
    }
}

Consider an example:

Original List: 5, 3, 8, 4, 2

Pass 1:

• Element 3 is compared with 5 and inserted before it (List: 3, 5, 8, 4, 2)

Pass 2:

• Element 8 is compared with 5 and 3, and inserted in its correct position (List: 3, 5, 8, 4, 2)

Pass 3:

• Element 4 is compared with 8, 5, and 3, and inserted in its correct position (List: 3, 4, 5, 8, 2)

Pass 4:

• Element 2 is compared with 8, 5, 4, and 3, and inserted in its correct position (List: 2, 3, 4, 5, 8)

• Worst and average case: O(n^2)
• Best case: O(n) when the list is nearly sorted

• O(1) - Insertion Sort is an in-place sorting algorithm.

• Insertion Sort is a stable sorting algorithm, meaning the relative order of equal elements remains unchanged after sorting.