Insertion Sort

Insertion sort is effective in sorting small lists and is often used to improve merge sort. Now,Every repetition of insertion sort removes an element from the input data, inserting it into the correct position in the already-sorted list, until no input elements remain.

becomes

The time complexity is O(n*log(n)) but it in general in writes to array O(n^2) times whereas selection sort writes only O(n) times.

void insertionSort(int a[], int n)
{
    int temp;
    for(int i=1; i<n; i++)
    {
        temp = a[i];
        int j=i-1;
        while(temp<a[j] && j>=0)
        {
            a[j+1] = a[j];
            j--;
        }
        a[j+1] = temp;
    }
}