Insertion Sort Algorithm in Java with Example and Explanation

The Insertion sort is another simple sorting algorithm, which can be used to sort any linear data structure like an array or linked list. On simplicity, this is next to bubble sort, and it’s also pretty close to how humans manually sort something (for example, a hand of playing cards). As the name suggests, the Insertion sort is based upon the insertion of an element in a sorted list. To start, we assume that the first element is already sorted. Then we pick the next element and put it in second place, we compare this number with the first element and if they are not in sorted order, we swap them. This gives a new sorted list of 2 elements.

Now we pick the third element and put it in the 3rd place and compare it with the 2nd placed number, if they are not in sorted order, we swap them again, if all three elements are still not in sorted order then we again swap the 1st and 2nd element, now we have a sorted list of three numbers.

This is how insertion sort progress i.e. you pick an element from the array, compare with already sorted ones and move them forward if they are greater than current element until you find the right place for your current element.

So in the best case, we just need one comparison and no swapping, while In the worst case we need to compare a new number with each number in the sorted list i.e. k comparison, and k -1 swapping, where k is the length of a sorted list.

Also, basic knowledge of essential data structure is also very important and that's why I suggest all Java programmers join a comprehensive Data Structure and Algorithms courses to fill the gaps in your understanding.

How does the Insertion Sort Algorithm work

I think Insertion sort is pretty easy to understand, isn't it? if you still don't get how the insertion sort algorithm works then let me remind you a real-life example of insertion sort.

Do you remember how you arrange your hand of cards in childhood?  You first pick one card, then pick the next card and put it after the first card if it is bigger or before the first card if it is smaller; then you pick another card and insert it into its proper position.

One more real-world example of insertion sort is how tailors arrange shirts in a cupboard, they always keep them in sorted order of size and thus insert new shirts at the right position very quickly by moving other shirts forward to keep the right place for a new shirt.

By the way, if you notice the trend then you can see that as the length of our sorted list increased, so as the number of comparison and swapping, which means this sorting algorithm is not suitable for large data set.

Indeed, it’s not as good as quick sort, heap sort, or mergesort for sorting large arrays, but it’s good enough to sort small integer arrays where the cost of comparison is small.

By the way, this algorithm is not just bound to numbers or integers, you can also sort String array with insertion sort or any list of Employee, depending they implement Comparator or Comparable to provide comparison logic.


Insertion sort can also be used to sort any List of elements in Java. We will see more advantages and disadvantage of insertion sort in the next section, for now, let's see the pseudo code for insertion sort algorithm.

If you still don't get how this algorithm works, then I suggest you read Grokking Algorithms by Aditya Bhargava, an easy to understand book which will help you to digest algorithms. Aditya has done a fabulous job to explain algorithms to even naive programmers.

Pseudo Code for Insertion sort

As I said on insertion sort we assume the first element is already sorted, what this mean to us is that we don't need to start at first element, so loop starts from the 2nd element. Since array index is zero based in Java, our pseudo code starts with i=1 (2nd index). Here is n is the total number of element i.e. length of the array.

// outer loop for going through each element

for i=1 to n-1 {
   int current = A[i];
   j = i ;

   // insertion and comparison

    while(j> 0) and A[j-1] > current{

        swap(A[j-1], A[j]);

        j = j -1;

    }

}

You can see that we go through each element and compare whether it is in proper position or not. Swapping only occurs if the element is not at its right position. This would be very clear by looking at insertion sort in action using GIF images.

To be frank, animation has helped me a lot to understand how a particular algorithm works. Your mind likes to see things moving and if you have a good animation or video tutorial for any algorithm, use that. One more thing which helped me a lot is creating flow charts.

Once you understand the algorithm, try creating a flowchart of logic by your own, this will ensure that your mind uses the knowledge you just learned, a signal that this is a useful stuff. This eventually helps to retain knowledge for a long time.  The Grokking Algorithm book work on the same principle, it's like the Head First guide of Algorithm.

Insertion Sort in Action

Here is an illustration or example of how insertion sort algorithm works. In this image, we have an unsorted array of integers. The first element in the array is 6, we assume it is sorted and on its proper position. Now next element is 5, if we have to sort the array in increasing order, we will compare 5 with 6, since 5 is less than 6, it will shift and 5 will take place of 6. Now next element is 3, we again compare 6 with 3, since 3 is less than 6, 6 will shift in place of 3; then again 3 will be compared to 5, again 5 will shift and 3 will take place of 5. This comparison and shifting will take place until we reach at the end of the array. At this time your array is sorted.
Since a picture is worth a thousand word, just follow below animation and you will learn what I am saying. If you miss the start, just refresh the page and animation will start again from the first element.

Insertion Sort implementation in Java

In this Java program, we will sort an integer array using Insertion sort algorithm in Java. As I said, insertion sort should only be used with small arrays or linked list, we are going to use an integer array of length 7, which contains numbers in random order.

We have a method called insertionSort(int[] input) which takes an unsorted array and sorts it. If you look at the logic, you will first see that we are looping over integer array, starting from the second element.

On inner loop, we initialize the index with next element e.g. in the first iteration, j=1 and it will point to the second element. The inner loop is used to compare current element with the already sorted element, that's why after each iteration we decrease j by 1, here j>0 condition stops when we reach the beginning of the array.

Shifting and swapping of element occur only if the current element is less than the already sorted element. Like in our code example, 32 is the first element so it is sorted, next is 23 so we compare it to 32, now 23 is less than 32 so we will swap 32 and 23 positions.

I have inline swapping logic but you can also create a method swap just to make the algorithm more readable. If you don't understand how swapping of integer works, then see this article. Once we came out of the outer loop, our int array is sorted in ascending order.

import java.util.Arrays;

/**
 * Java program to implement insertion sort in Java. In this example, we will
 * sort an integer array using insertion sort algorithm. This logic can be used
 * to sort array of String, or any other object which implements Comparable or
 * Comparator interface in Java.
 * 
 * @author Javin Paul
 */

public class Pattern {
  public static void main(String args[]) {
    // unsorted integer array
    int[] unsorted = { 32, 23, 45, 87, 92, 31, 19 };
    System.out.println("integer array before sorting : "
                          + Arrays.toString(unsorted));

    insertionSort(unsorted);

    System.out.println("integer array after sorting : "
                          + Arrays.toString(unsorted));
  }

  /*
   * Sort given integer array using Insertion sort algorithm. only good for
   * small arrays.
   */

  public static void insertionSort(int[] unsorted) {
    for (int i = 1; i < unsorted.length; i++) {
      int current = unsorted[i];
      int j = i;

      // create right place by moving elements
      while (j > 0 && unsorted[j - 1] > current) {

        // move
        unsorted[j] = unsorted[j - 1];
        j--;
      }

      // found the right place, insert now
      unsorted[j] = current;
    }
  }
}

Output
integer array before sorting : [32, 23, 45, 87, 92, 31, 19]
integer array after sorting : [19, 23, 31, 32, 45, 87, 92]

Complexity Analysis

Once you know how an algorithm works, next task is to figure out its time and space complexity. If you have been asked to write insertion sort algorithm on an interview, rest assured that interviewer will ask you to calculate the best case, average case, and worst case time and space complexity.

If you have understood algorithm correctly then it shouldn't be difficult. Just think, what would be the best case for sorting, an already sorted array right? So suppose you get an already sorted array, how will insertion sort work there? it assumes that the first element is sorted, so it will pick next element and compare it with the first element since it's sorted list this will be greater than first element and no swapping will occur.

In the end only n - 2 comparison will be required and no swapping. This means an O(n) time complexity in the best case.

Now, what would be the worst case for sorting an array, an already sorted list but in reverse order? Again, the first iteration will start with the second number, to sort this we need 1 comparison and 1 swapping, for 2nd iteration and to sort 3rd element we will be needing 2 comparisons and 2 shifting.

So for n-1 iteration, you will need n comparison and n shift. which means O(n^2) time complexity. The average case is in between best and worst case, which is again in order of  O(n ^2). This is the main reason why insertion sort is not suitable for sorting the large array because to sort 100 numbers, you will be needing time in order of 100*100.

I also suggest reading Data Structure and Algorithm Made Easy in Java by Narasimha Karumanchi to learn more about how to calculate time and space complexity of an algorithm.

Advantages and Disadvantages of Insertion Sort Algorithm

Insertion sort has the advantage of the already sorted list over Bubble Sort algorithm. It requires fewer comparison then bubble sort unless the list is backward. If an array is already sorted then we only make n comparison, i.e. one comparison per element. With a sorted array, which just needs to keep inserting elements. Insertion sort has following advantages compared to other similar sorting algorithms

1) Simple implementation, Insertion sort is next to bubble sort in simplicity. In classes and training, it is taught along with selection sort and quick sort.

2) Insertion sort is efficient for small arrays but not suitable for large data sets. Don't use insertion sort in production code, instead use Collections.sort() method, which is based on merge sort. Alternatively, you can also use quicksort for sorting any array or List in Java.

3) Insertion sort is additionally efficient for lists that are already substantially sorted. In those cases, time complexity is O(n + d), where d is the number of inversions.

4) Insertion sort is more efficient in practice than most other quadratic or O(n^2) algorithms such as selection sort and bubble sort; the best case complexity for a nearly sorted array is O(n).

5) Insertion sort is stable sorting algorithm i.e. it does not change the relative order of elements with equal keys

6) Insertion sort does In-place sorting; which means this algorithm only requires a constant amount O(1) of additional memory space


That's all about Insertion sort in Java. It's one of the fundamental algorithms and as a Java developer, you should know how to write code to sort an integer array using insertion sort. This is quite often asked in Java interviews and written test.  If you want to learn more about Insertion sort and other comparison-based sorting algorithm, then you can read Introduction to Algorithms by Thomas H. Cormen. It has helped me to learn understanding algorithm as well as calculating time complexity of them.


Related Data Structure and Algorithm Interview Questions from Javarevisited Blog

• Top 15 Data Structure and Algorithm Interview Questions (see here)
• Top 20 String coding interview questions (see here)
• 133 core Java interview questions of last 5 years (see here)
• Top 30 Array Coding Interview Questions with Answers (see here)
• Top 30 linked list coding interview questions (see here)
• Top 50 Java Programs from Coding Interviews (see here)
• Top 5 books on Programming/Coding Interviews (list)

Thanks for reading this article so far. If you like this article then please share with your friends and colleagues. If you have any question or doubt then please let us know and I'll try to find an answer for you.