Insertion Sort

#include <bits/stdc++.h>

using namespace std;

int main()

{

    int n, i, j, value;

    cout << "Enter the size of array : ";

    cin >> n;

    int a[n];

    cout << "\nEnter the array : ";

    for (i = 0; i < n; i++)

        cin >> a[i];

    for (i = 1; i < n; i++)

    {

        value = a[i];

        j = i - 1;

        while (j >= 0 && a[j] > value)

        {

            a[j + 1] = a[j];

            j--;

        }

        j += 1;

        a[j] = value;

    }

    cout << "\nThe Sorted array will be : \n";

    for (i = 0; i < n; i++)

        cout << a[i] << " ";

}

# Start from the i=2nd value, store it in another variable (X) and

keeping on replacing the values from left to right until you find a value

less than the value stored in X or array gets over. Let that smaller value

be at index (j) and (-1) if the array got over. Then move (j) ahead (j++)

and store the value of (X) at new position pointed by (j).

Now do similar for i=3rd,4th,.....n-1th term.