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) = n2 In this case, the worst-case complexity will be O(n2).
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
See you in another article,
Onur Baskirt
Onur Baskirt is a Software Engineering Leader with international experience in world-class companies. Now, he is a Software Engineering Lead at Emirates Airlines in Dubai.