Insertion sort in java

Let’s learn insertion sort in java.

Insertion sort in java

Insertion sort sorts elements the way in which we sort playing cards. This sort can be fast when used with smaller arrays.

Given an array of elements, let’s sort them in increasing order. So let’s look at sample list of integer elements. We have an array of six elements that we want to sort.

Insertion sort algorithm:

Insertion sort iteration starts at index 1 which is 80. So we will set our key value x = 80. Now our first comparison is to the element which is to the left of the key value, that is, 50.

Now, is x < 50? In other words, is 80 < 50? No. So, 80 is going to stay where it is. Then we will look at index 1 in the array which is 10. We will assign key value x = 10. Now, is x < 50? Yes it is, 10 < 50. So swap 50 and 10.

So we are going to jump to index 3 which is 30. So, we set our key value x = 30. Now, is x < 80? Yes it is, swap 30 and 80. Next comparison, is 30 < 50? Yes, swap those two numbers.

Next comparison, is 30 < 10? No it’s not, so we are done sorting upto index 3. So the values to the left of 80 are all smaller. Our next element in the array is 90, we set x = 90.

Now, is x < 80? No. So we move on to index 5 which is 60. We set key value x = 60.

Now, is 60 < 90? Yes it is, swap them. Next comparison, is 60 < 80? Yes it is, swap 60 and 80. We have our sorted array (as shown in above figure). Here’s the insertion sort program in java.

class InsertionSortExample 
{
   public static void main(String[] args) 
   {
      int[] arrInput = { 50, 80, 10, 30, 90, 60 };
      int keyValue, b;
      for (int a = 1; a < arrInput.length; a++)
      {
         keyValue = arrInput[a];
         b = a;
         while (b > 0 && arrInput[b - 1] > keyValue)
         {
            arrInput[b] = arrInput[b - 1];
            b--;
         }
         arrInput[b] = keyValue;
      }
      for (int i = 0; i < arrInput.length; i++)
      {
         System.out.print(arrInput[i] + " ");
      }
   }
}

Output:

10 30 50 60 80 90

Time complexity

Insertion sort algorithm takes more time if elements in the array is in reverse order.

Best time complexity: O(n) comparison and O(1) swap.

Worst time complexity: O(n²) comparison and swap.

Average time complexity: O(n²) comparison and swap.

Space complexity: O(1) because an extra variable key is used.

Auxiliary space: O(1)