Insertion Sort Algorithm in Java | Visualization and Examples

In this tutorial, we will learn what the insertion sort algorithm is, how it works, its space and time complexities, and insertion sort implementation in Java.

What is Insertion Sort Algorithm?

Insertion sort is a sorting algorithm that works by inserting the index to be sorted element to its correct position based on comparisons with the other elements.

Before starting the sorting, we assume that the index 0 is already sorted and then we have an iteration from index 1 to n-1 and in each iteration, we have an inner loop from right to left to do comparisons to insert the unsorted element to the correct position.

How Does Insertion Sort Work?

I will explain the Insertion sort algorithm in ascending order. Let’s assume that we have an unsorted array as follows: [18, 32, -11, 6, 68, 2, -34]

We assume that the first element which is index 0 is already sorted and we start the higher-level iteration from index 1 to index n-1 (n is the length of the array) which is 6 in our case. 

In each iteration of 1 to n-1;

• First, we save the value at starting index to sort in a variable which I called “startingIndexToSort”.

We have an inner iteration that is starting from startingIndexToSort and we check two conditions:

• The iteration index “i” should be greater and equal to 1.
• The value at starting Index to sort is smaller than the value at array[i -1].

If these two conditions are met, then we will do the below assignment:

• array[i] = array[i – 1];

If these conditions are not met, we will assign the array[i] to value at starting Index to sort.

Insertion Sort Visualization

Our unsorted array of numbers is as follows:

We assume that the index 0 is sorted and we start the high-level iteration from 1 to 6. I will explain the details for each iteration.

First Iteration

At the first iteration, startingIndexToSort is 1 and its value is 32. We keep this value as “valueAtStartingIndexToSort”.

Then, we iterate from 1 until current index (i) bigger or equal to 1 and valueAtStartingIndexToSort < array[i-1].

The iteration index (i) is 1 and the valueAtStartingIndexToSort (32) is not smaller than the array[0] (18) that’s why we skip the for loop, and nothing changes in the array. Our aim is to do an ascending sort and for 18 and 32 this order already correct.

Second Iteration

At the second iteration, startingIndexToSort is 2 and its value is -11. We keep this value as “valueAtStartingIndexToSort”.

Then, we iterate from 2 until current index (i) bigger or equal to 1 and valueAtStartingIndexToSort < array[i-1]. 

When the iteration index (i) is 2, -11 is smaller than 32 and we do the below assignment:

array[i] = array[i – 1];  ->  array[2] = array[1]; 

When the iteration index (i) is 1, -11 is smaller than 18 and we do the below assignment:

array[i] = array[i – 1];  ->  array[1] = array[0]; 

When the iteration index (i) is 0 the for loop is finished because 0 is not bigger or equal to 1 and we do the final assignment.

array[i] = valueAtStartingIndexToSort; -> array[0] = -11

Third Iteration

At the third iteration, startingIndexToSort is 3 and its value is 6. We keep this value as “valueAtStartingIndexToSort”.

Then, we iterate from 3 until current index (i) bigger or equal to 1 and valueAtStartingIndexToSort < array[i-1]. 

When the iteration index (i) is 3, 6 is smaller than 32 and we do the below assignment:

array[i] = array[i – 1];  ->  array[3] = array[2]; 

When the iteration index (i) is 2, 6 is smaller than 18 and we do the below assignment:

array[i] = array[i – 1];  ->  array[2] = array[1]; 

When the iteration index (i) is 1, 6 is NOT smaller than -11, and for loop is terminated and we do the final assignment.

array[i] = valueAtStartingIndexToSort; -> array[1] = 6

Fourth Iteration

At the fourth iteration, startingIndexToSort is 4 and its value is 68. We keep this value as “valueAtStartingIndexToSort”.

Then, we iterate from 4 until current index (i) bigger or equal to 1 and valueAtStartingIndexToSort < array[i-1]. 

When the iteration index (i) is 4, 68 is NOT smaller than 32, and for loop is terminated.

Fifth Iteration

At the fifth iteration, startingIndexToSort is 5 and its value is 2. We keep this value as “valueAtStartingIndexToSort”.

Then, we iterate from 5 until current index (i) bigger or equal to 1 and valueAtStartingIndexToSort < array[i-1]. 

When the iteration index (i) is 5, 2 is smaller than 68 and we do the below assignment:

array[i] = array[i – 1];  ->  array[5] = array[4]; 

When the iteration index (i) is 4, 2 is smaller than 32 and we do the below assignment:

array[i] = array[i – 1];  ->  array[4] = array[3]; 

When the iteration index (i) is 3, 2 is smaller than 18 and we do the below assignment:

array[i] = array[i – 1];  ->  array[3] = array[2]; 

When the iteration index (i) is 2, 2 is smaller than 6 and we do the below assignment:

array[i] = array[i – 1];  ->  array[2] = array[1]; 

When the iteration index (i) is 1, 2 is NOT smaller than -11 and for loop is terminated and we do the final assignment.

array[i] = valueAtStartingIndexToSort; -> array[1] = 2

Sixth Iteration

At the sixth iteration, startingIndexToSort is 6 and its value is -34. We keep this value as “valueAtStartingIndexToSort”.

Then, we iterate from 6 until current index (i) bigger or equal to 1 and valueAtStartingIndexToSort < array[i-1]. 

When the iteration index (i) is 6, -34 is smaller than 68 and we do the below assignment:

array[i] = array[i – 1];  ->  array[6] = array[5]; 

When the iteration index (i) is 5, -34 is smaller than 32 and we do the below assignment:

array[i] = array[i – 1];  ->  array[5] = array[4]; 

When the iteration index (i) is 4, -34 is smaller than 18 and we do the below assignment:

array[i] = array[i – 1];  ->  array[4] = array[3]; 

When the iteration index (i) is 3, -34 is smaller than 6 and we do the below assignment:

array[i] = array[i – 1];  ->  array[3] = array[2]; 

When the iteration index (i) is 2, -34 is smaller than 2 and we do the below assignment:

array[i] = array[i – 1];  ->  array[2] = array[1]; 

When the iteration index (i) is 1, -34 is smaller than -11 and we do the below assignment:

array[i] = array[i – 1];  ->  array[1] = array[0]; 

After this iteration index becomes 0 and we break the inner loop and finally, we assign the array[i] to valueAtStartingIndexToSort.

array[i] = valueAtStartingIndexToSort; -> array[0] = -34

Insertion Sort Animation

Insertion Sort in Java

 I will share with you insertion sort implementations in Java in ascending order. 

Insertion Sort Java Implementation in Ascending Order with For Loop

public static int[] ascendingInsertionSort(int[] array) {
    //Insertion sort in ascending order with for loop.
    for (int startingIndexToSort = 1; startingIndexToSort < array.length; startingIndexToSort++) {
        int valueAtStartingIndexToSort = array[startingIndexToSort];
        int i;
        for (i = startingIndexToSort; i >= 1 && valueAtStartingIndexToSort < array[i - 1]; i--) {
            array[i] = array[i - 1];
        }
        array[i] = valueAtStartingIndexToSort;
    }
    return array;
}

Output

Insertion Sort Java Implementation in Ascending Order with While Loop

public static int[] ascendingInsertionSortWithWhile(int[] array) {
    //Insertion sort in ascending order with while loop.
    for (int startingIndexToSort = 1; startingIndexToSort < array.length; startingIndexToSort++) {
        int valueAtStartingIndexToSort = array[startingIndexToSort];
        int i = startingIndexToSort;
        while (i >= 1 && valueAtStartingIndexToSort < array[i - 1]) {
            array[i] = array[i - 1];
            i--;
        }
        array[i] = valueAtStartingIndexToSort;
    }
    return array;
}

Output

The Complexity of Insertion Sort

In this part, I will explain the time and space complexity of the insertion sort algorithm.

Time Complexity

Worst Case Time Complexity of Insertion Sort

When we do a sort in ascending order and the array is ordered in descending order then we will have the worst-case scenario.  for every nth element, (n-1) number of comparisons are made. Thus, the total number of comparisons = n*(n-1) = n² In this case, the worst-case complexity will be O(n²).

Best Case Time Complexity of Insertion Sort

If the given array is already in sorted order, insertion sort compares O(n) elements but in this case, the inner loop does not run, and this time the complexity becomes O(n).

Space Complexity

The space complexity of the Insertion sort is O(1). It is a stable sorting algorithm as well.

When Can We Use Insertion Sort?

Insertion sort runs faster in best-case and it is a good sorting algorithm when the array is already sorted. When the array is unsorted, the average or worst-case running time occurs.

GitHub Project

Insertion Sort Implementation in Java

In this article, I have shared what insertion sort is, how it works, its complexities, and its implementations. I also tried to visualize the insertion sort algorithm with colorful diagrams to make it as clear as possible. I hope you enjoyed reading this article.

Other Sorting Algorithms Articles

• Bubble Sort

• Selection Sort

See you in another article,
Onur Baskirt