insertion sort

It is a simple sorting algorithm in which array is split into two parts ,first part is sorted  and an another part is unsorted . Values from the unsorted part are picked and placed at the correct position in the sorted part. 

Algorithm
first divide the array into sorted and unsorted array ,in sorted array only one element is present in the beginning ie. arr[0] (as only one element is always sorted) and in unsorted array the remaining elements from arr[1] to arr[n]
1: Iterate from arr[1] to arr[n] over the unsorted array.
2: store the current element in temp variable now compare the temp variable to all the elements in the sorted array starting from rightmost element
3:if temp is smaller than those elements we move that particular element to right by one position
4: till we find temp greater than any element in sorted array we will continue the above step 3
5: once the temp is greater than any of these elements , we move that element to one position right and place temp in that particular position

lets take an example and see how insertion sort works:

 green line is used to divide the array in sorted and unsorted part 

 yellow box represents the element to be checked and kept in temp variable

implementation: 

void insertionSort(int arr[], int n)  
{  
    int  temp, j;  
    for (int i = 1; i < n; i++) 
    {  
        temp = arr[i];  
        j = i - 1;  
  
        /* Move elements of arr[0..i-1], that are  
        greater than temp, to one position ahead  
        of their current position */
        while (j >= 0 && arr[j] > temp) 
        {  
            arr[j + 1] = arr[j];  
            j = j - 1;  
        }  
        arr[j + 1] = temp;  
    }  
}  

Time Complexity: O(n*2)

Auxiliary Space: O(1)