Implementation



#include <iostream>
using namespace std;
void insertion_sort(int A[], int n)
{
    for (int i = 0; i < n; i++)
    {

        int temp = A[i];
        int j = i;
        while (j > 0 && temp < A[j - 1])
        {
            A[j] = A[j - 1];
            j--;
        }
        A[j] = temp;
    }
}
int main()
{
    int arr1[] = {22, 33, 29, 49, 21, 57, 62, 73, 54, 44};
    int n = 9;
    insertion_sort(arr1, n);
    cout << "array :" << endl;
    for (int i = 0; i < n; i++)
    {
        cout << arr1[i] << " ";
    }

    return 0;
}


Output


Sorted array :
21 22 29 33 49 54 57 62 73

Time Complexity: O(N^2)