class Solution
{
    public:
    void insertionSort(int arr[], int n)
    {
        int value,hole;
        for(int i=0;i<n;i++){
            value=arr[i];hole=i;
        while(hole>0&&arr[hole-1]>value){
            arr[hole]=arr[hole-1];
            hole--;
        }
        arr[hole]=value;
        }
    }
};