Insertion Sort Algorithm

Insertion Sort Algorithm start sorting from one end and traverse through the Insertion Sort Algorithm start sorting from one end and traverse through the array while ensuring the elements already read are in the correct order.

Take the first element of the array, consider it as sorted.

Then take the second element compare it with the previous if the first element is greater than the second then move the first element one cell backward and insert the second element in the first cell. Then we have a sorted array of two elements.

Then consider the third element and compare it with values of the previous cells move any element with value greater than the current element one cell forward and inset the current value in the correct place, this step results an array of three elements that are in the correct order.

Repeat these steps for all the elements in the array.

Insertion Sort Algorithm, C++ implementation

void InsersionSort(int* A, int length)
{
    int temp = 0;
    for (int i = 0; i < length; i++)
    {
        for (int j = i; j > 0; j--)
        {
            if (A[j - 1] > A[j])
            {
                temp = A[j - 1];
                A[j - 1] = A[j];
                A[j] = temp;
            }
        }
    }
}