---

Insertion sort is a simple sorting algorithm that works the way we sort playing cards in our hands. This is an in-place comparison-based sorting algorithm. Here, a sub-list is maintained which is always sorted. For example, the lower part of an array is maintained to be sorted. An element which is to be inserted in this sorted sub-list, has to find its appropriate place and then it has to be inserted there. Hence the name, insertion sort.

Algorithm for insertion sort

Now we have a bigger picture of how this sorting technique works, so we can derive simple steps by which we can achieve insertion sort.

Step 1 ? If it is the first element, it is already sorted. return 1;
Step 2 ? Pick next element
Step 3 ? Compare with all elements in the sorted sub-list
Step 4 ? Shift all the elements in the sorted sub-list that is greater than the 
         value to be sorted
Step 5 ? Insert the value
Step 6 ? Repeat until list is sorted

InsertionSort(A){

for j = 2 to A.lenght
key = A[j]
//insert A[j] into sorted sequence A[1,2......,j-1] 
 i = j-1
 
 while(i > 0 and A[i] > key)
  {
  A[i+1] = A[i]
  i = i-1
  }
  
 A[i+1] = key 

} 

Time Complexity for insertion sort algorithm

The array is searched sequentially and unsorted items are moved and inserted into the sorted sub-list (in the same array). This algorithm is not suitable for large data sets as its average and worst case complexity are of ?(n²), where n is the number of items.

Case	Complexity
Worst Case	?(n2))
Best Case	O(n)

Space Complexity for insertion sort algorithm

Space Complexity for insertion sort algorithm is

Case	Complexity
Worst Case	O(1)

Implementation in C

// C program for insertion sort
#include 
#include 
 
/* Function to sort an array using insertion sort*/
void insertionSort(int arr[], int n)
{
   int i, key, j;
   for (i = 1; i < n; i++)
   {
       key = arr[i];
       j = i-1;
 
       /* Move elements of arr[0..i-1], that are
          greater than key, to one position ahead
          of their current position */
       while (j >= 0 && arr[j] > key)
       {
           arr[j+1] = arr[j];
           j = j-1;
       }
       arr[j+1] = key;
   }
}
 
// A utility function to print an array of size n
void printArray(int arr[], int n)
{
   int i;
   for (i=0; i < n; i++)
       printf("%d ", arr[i]);
   printf("\n");
}
 
 
 
/* Driver program to test insertion sort */
int main()
{
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
 
    insertionSort(arr, n);
    printArray(arr, n);
 
    return 0;
}

What is Binary Insertion Sort?
We can use binary search to reduce the number of comparisons in normal insertion sort. Binary Insertion Sort find use binary search to find the proper location to insert the selected item at each iteration. In normal insertion, sort it takes O(i) (at ith iteration) in worst case. we can reduce it to O(logi) by using binary search. The algorithm as a whole still has a running worst case running time of O(n2) because of the series of swaps required for each insertion. 

---