Insertion Sort

InsertionSort.cpp

void insertionSort(vector<int>& arr){
   
    int lastIndex = arr.size() - 1;
    
    // Repeat from second element to last element.
    for(int i = 1; i <= lastIndex; i++){
        
        // Store the current element in a variable.
        int element = arr[i];
        
        // Find right index where element can fit in and make space for it.
        // By shifting all other sorted elements by one place which is after.
        // te destination index for element.
        int j = i-1;
        while(j>=0){
            if(arr[j]>element){
                arr[j+1] = arr[j];
                j--;             // Decreasing j so that we will check for element before it.
            }else{
                // if element is already bigger than this element then we wont check for further element
                // and current j's very next index is correct index where the element should be put.
                break;
            } 
        }
        
        // Place element in destination.
        arr[j + 1] = element;
    }
    
}