What is Insertion sort and how it works ?

Insertion sort - Complexity O(n^2)

• Insert the element at right place in the left part (for one index per pass)
• Repeat from index 1 to n-1
• Compare element with all its previous items until we receive a lesser value
• Swap if current element is less than previous one

Java code

// Loop from 1 to n-1

for (int i=1; i ‹ array.length; i++) {
   int element = array[i];

   // Loop through previous elements till first element or lower item found

   int j = i;
   while (j > 0 && array[j-1] > element) {
        array[j] = array[j-1];   // Swap - first part
        j--;
   }
   array[j] = element;   // Swap - second part
}

Example

29, 20, 73, 34, 30 

20, 29, 73, 34, 30 
20, 29, 73, 34, 30 
20, 29, 34, 73, 30 
20, 29, 30, 34, 73

Highlighted are swapped during each pass