Insertion Sort with Java

The insertion sort is one of the simplest sorting algorithms available. It’s also one of the least efficient in terms of performance.

The insertion algorithm will go through the whole array with the index i starting with 1 and then sort elements to the left side using the j index. The index i will be increased to the end of the array and the j index will be decreased to the beginning of the array if there are elements to be sorted to swap the array elements that are not sorted.

The left side will be fully sorted to the left in each iteration of the index i. If the elements from the left are already sorted then the index i will be increased.

To describe this process, let’s see the following diagram:

Let’s see now how it works in code:

public class InsertionSort {

  public static void main(String[] args) {
    int[] array = {1, 5, 2, 3, 12, 8};
    var sortedArray = InsertionSort.sort(array);
    System.out.println(Arrays.toString(sortedArray));
  }
  
  public static int[] sort(int[] array) {
    for (int i = 1; i < array.length; i++) {
      var j = i;
      while (j > 0 && array[j - 1] > array[j]) {
        swap(array, j);
        j--;
      }
    }

    return array;
  }

  private static void swap(int[] array, int j) {
    var temp = array[j];
    array[j] = array[j - 1];
    array[j - 1] = temp;
  }

}

Output:
[1, 2, 3, 5, 8, 12]

Code analysis:

Firstly in the sort method, we will iterate starting from 1 to the end of the array. Then j receives the value of i. In the while looping, we check if j is greater than 0 and if the array in the index of j – 1 is greater than the array in the index of j. If that is true the array values will be swapped.

If the left part of the array is already sorted, the index i will be increased by 1.

This algorithm is very similar to the Bubble sort, as you can see it’s straightforward.

Big(O) Notation

Time Complexity: this algorithm requires two loopings to sort the algorithm. For each looping interaction, the second looping will run through all the array elements. The performance is really bad, it’s O(n^2). This means that it’s n * n. Suppose there are 10 array elements, the arrays can be traversed 100 times because 10 * 10 is 100. Remember that the time complexity is usually measured in the worst-case scenario. The whole array has to be unsorted so the array will be traversed something around 100 times.

Space Complexity: in terms of space this algorithm is efficient. It sorts the array in place, this means that there is no need to store elements in an auxiliary array. Therefore, since one element is swapped each time, the space complexity is O(1).

Summary

The insertion algorithm will traverse an array from the beginning to the end and then will sort elements to the left side until the array is fully sorted.

• The index of i starts with 1 since the second element from the array has to be compared with the first one.
• The index of j will start with the same value of i and will be decreased by comparing the elements from the left side of the array.
• When a comparison from the left side of the array using the index of j is false, the index of i is increased to perform a comparison with a new element value. That’s because since the left array is already sorted, we know that if a comparison returns false, this element will for sure be greater than the other elements from the left.