Insertion Sort

This is an in-place comparison-based sorting algorithm. Here, a sub-list is maintained which is always sorted. The left part of the array is maintained to be sorted.

An element which is to be inserted in this sorted sub-list, has to find its approate place and then it has to be inserted there.

Time Complexity: average and worst case are both O(n2).

void insertionSort(vector<int> &arr) {
   int i, key, j;
   for (i = 1; i < n; i++) {
       key = arr[i];
       j = i-1;

       while (j >= 0 && arr[j] > key) {
           arr[j+1] = arr[j];
           j = j-1;
       }
       arr[j+1] = key;
   }
}