Insertion sort

Prerequisite: 
Algorithm, Sorting, Asymptotic complexity(time complexity, space complexity)

Introduction:
Insertion sort will take elements from 0 to n and compare & swap it with the left part of the array which is already sorted among the elements, until it find the right place where the element has to be. You may be clear, when look at the below code,

Code:

public int[] doInsertionSort(int[] ip) {
 for(int i =1;i<ip.length;i++) {
  for(int j=i;j>0;j--) {
   if(ip[j]<ip[j-1]){
    swap(ip, j, j-1);
   }else {
    break;
   }
  }
 }
 return ip;
}

Performance:
Time complexity of this sorting is O(n²) in a worst case scenario, O(n) in a best case scenario. O(n), when the array is already sorted. Worst case space complexity is O(1).

Where/when to use:
Even though it took more time or steps to sort the list than the other algorithms like Heap & merge sort, we still can use it in some places.It’s easy to implement as selection sort, so we can use this for smaller arrays. But it may do more swaps than selection sort.
It’s good to use this sort in a place where the element are all already sorted.Let’s consider you already have a sorted list & a new element is added to the list. So now u need to place the last element in right place to make the list sorted again.