Insertion Sort Algorithm in Java with Example

Insertion sort is another simple sorting algorithm like Bubble Sort. You may not have realized but you must have used Insertion sort in a lot of places in your life. One of the best examples of Insertion sort in the real-world is, how you sort your hand in playing cards. You pick one card from the deck, you assume it's sorted, and then we insert subsequent cards in their proper position. For example, if your first card is Jack, and the next card is Queen then you put the queen after Jack. Now if the next card is King, we put it after the queen, and if we get 9, we put it before jack.

So if you look closely, Insertion sort is a perfect sorting algorithm to insert a new value into an already sorted array. That's why the best-case complexity of insertion sort is O(n), in which case you can just insert a new number in the already sorted list of integers.

Another thing to keep in mind is the size of the list, insertion sort is very good for small list or array, but not so for a large list, where QuickSort, MergeSort, and HeapSort rules.

Let's see one more example of insertion sort from real life. Have you noticed, how do tailors arrange customers' shirts in their wardrobe, according to size. So they insert a new shirt at the proper position, for that, they shift existing shirts until they find the proper place.

If you consider wardrobe as an array and shirts as an element, you will find out that we need to shift existing elements to find the right place for the new element. This is the core of the insertion sort algorithm, if you understand these examples, even you can come up with a step-by-step coding algorithm to sort an array of an integer using insertion sort in Java.

In this article, we will learn that by first understanding insertion sort with flowchart and by walking through an example. After that writing, a Java method to do insertion sort will be very easy.

Btw, If you are a complete beginner into data structure and algorithms then I suggest you join a comprehensive course like Data Structures and Algorithms: Deep Dive Using Java on Udemy, which will not only teach you the Insertion sort algorithms but also other essential data structure and sorting algorithms. It's one of my favorite courses on this topic

How the Insertion Sort Algorithm works

If you know how to sort a hand of cards, you know how insertion sort works; but for many programmers, it's not easy to translate real-world knowledge into a working code example.

This is where natural programming ability comes into play. A good programmer has the ability to code any algorithm and convert a real-life example to an algorithm.

Now, how do you sort an array of an integer using this algorithm? You can say that we can treat this array as a deck of cards, and we will use another array to pick and place an element from one place to another. Well, that will work, but it's a waste of space (memory) because what you are doing is comparing and shifting, which can also be done in place in the same array.

Here is the step by step guide to coding insertion sort algorithm in Java:

1) Consider the first element is sorted and it's in the proper place, that is index 0 for your array.

2) Now go to the second element (index 1 in the array), and compare it with what is in your hand (the part of the array, which is already sorted). This means you compare this element going backward towards index zero.

3) If the current number is smaller than the previous number (which is in the proper place), we need to put our current number before that. How will we do that? Well for that we need to shift the existing number.

But what if there is another element that is greater than our current element? It means we need to continue comparing until we found a proper place for our current number, which again means current number> existing number or we are at the start of the list (index 0 in the array).

4) You need to repeat this process for all the numbers in the list. Once you finish that, you have a sorted list or array.

In short, insertion sort is all about finding the proper place for the current number. Once you find the proper place, you need to shift the existing element to make a place for this new number.  If you want to learn more about Insertion sort and other sorting algorithms, you can also see the course Algorithms and Data Structures - Part 1 and 2 or a good book like Algorithms in Nutshell which is fantastic course to learn important Computer Science Algorithms.

A Visual Explanation of Insertion Sort Algorithm

It's said that "A picture is worth a thousand words", this is quite true in the case of understanding sorting algorithms. Earlier we had seen how easy it was to understand the QuickSort algorithm using a GIF image, and now we will again learn how Insertion sort works by following this diagram, It becomes extremely easy to explain how insertion sort works with this example.

Here we have an integer array of both positive and negative numbers in random order. Our task is to sort this unsorted array using Insertion Sort in ascending order, which means the smallest element should be at the start of the array and the largest element must be at the end of the array.

To start working we assume that our first element is in the proper position (remember the first card in your hand) and start with the second integer, which is  -5. Now we compare it with 7, since - 5 is less than 7, we first move 7 in place of -5.

After this, we don't need to compare -5 with any other number because we have reached the left boundary so we will put -5 at the current place. Now, we pick the third element which is 2. We compare 2 with 7 and found that 2 is also less than 7, which means 7 shifted in place of 2.

Next, we compare 2 with -5, now 2 is greater than -5 so we insert it at this place. After this, we pick the fourth element which is 16. Since 16 is greater than 7, no need to shift anyone, 16 will remain in its place.

Now last element 4, it is less than 16 to 16 will move in place of 4, next we compare 4 with 7, again 4 is less than so 7 will be shifted, after this we compare 4 with 2, wow it's greater than 2, so we have found a proper place for 4. We insert 4 there. Now there is no more element to process an array, so our array is now sorted.

You can see that at the last step our array is sorted in increasing order, starting from - 5 and ending at 16.

By the way, algorithms can be better understood by looking at a flowchart or a real example with numbers or by joining a good online course like Visualizing Data Structures and Algorithms in Java, which is also a great way to learn basic data structure and algorithms.

Insertion Sort in Java with Example

It's very easy to implement Insertion sort in Java.  All you need to do is to iterate over the array and find the proper position of each element, for that you need to shift the element and you can do it by swapping. The logic of sorting integer array using the insertion sort algorithm is inside method insertionSort(int[]).

In Java you can also sort any object e.g. String using this algorithm, all you need to do is to use a Comparable interface because that will provide you mechanism to compare two objects. Now instead of using > (greater than) or < (less than) operator, we need to use compareTo() method.

For this, we have decided to overload our insertionSort() method, where an overloaded version takes an Object array instead of an int array. Both methods sort elements using insertion sort logic.

By the way, in the real world, you don't need to reinvent the wheel, java.util.Arrays class provides several utility methods to operate upon arrays and one of them is sort.

There is a couple of overloaded version of sort() method available to sort primitive and object arrays. This method uses double-pivot QuickSort to sort the primitive array and MergeSort to sort object array.

Anyway, here is our complete code example to run the Insertion sort in Java. If you are using Eclipse IDE then just copy-paste the code in the src folder of your Java project and Eclipse will create packages and source files with the same name by itself. All you need to do is that run it as a Java program.

import java.util.Arrays;

/**
 * Java program to sort an array using Insertion sort algorithm.
 * Insertion sort works great with already sorted, small arrays but 
 * not suitable for large array with random order.
 *
 * @author Javin Paul
 */
public class InsertionSort {

  public static void main(String args[]) {

  // getting unsorted integer array for sorting
  int[] randomOrder = getRandomArray(9);
  System.out.println("Random Integer array before Sorting : " 
                          + Arrays.toString(randomOrder));

  // sorting array using insertion sort in Java
  insertionSort(randomOrder);
  System.out.println("Sorted array uisng insretion sort : " 
                            + Arrays.toString(randomOrder));

  // one more example of sorting array using insertion sort
  randomOrder = getRandomArray(7);
  System.out.println("Before Sorting : " + Arrays.toString(randomOrder));
  insertionSort(randomOrder);
  System.out.println("After Sorting : " + Arrays.toString(randomOrder));

  // Sorting String array using Insertion Sort in Java
  String[] cities = {"London", "Paris", "Tokyo", "NewYork", "Chicago"};
  System.out.println("String array before sorting : "
                           + Arrays.toString(cities));
  insertionSort(cities);

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

  public static int[] getRandomArray(int length) {
    int[] numbers = new int[length];
    for (int i = 0; i < length; i++) {
      numbers[i] = (int) (Math.random() * 100);
    }
    return numbers;
  }

  /*
  * Java implementation of insertion sort algorithm to sort
  * an integer array.
  */
  public static void insertionSort(int[] array) {
  // insertion sort starts from second element
  for (int i = 1; i < array.length; i++) {
    int numberToInsert = array[i];

    int compareIndex = i;
    while (compareIndex > 0 && array[compareIndex - 1] > numberToInsert) {
       array[compareIndex] = array[compareIndex - 1]; // shifting element
       compareIndex--; // moving backwards, towards index 0
    }

    // compareIndex now denotes proper place for number to be sorted
     array[compareIndex] = numberToInsert;
   }
 }

  /*
  * Method to Sort String array using insertion sort in Java.
  * This can also sort any object array which implements
  * Comparable interface.
  */
  public static void insertionSort(Comparable[] objArray) {
  // insertion sort starts from second element
  for (int i = 1; i < objArray.length; i++) {
      Comparable objectToSort = objArray[i];

      int j = i;
      while (j > 0 && objArray[j - 1].compareTo(objectToSort) > 1) {
         objArray[j] = objArray[j - 1];
         j--;
      }
     objArray[j] = objectToSort;
   }
 }

}

Output:
Random Integer array before Sorting : [74, 87, 27, 6, 25, 94, 53, 91, 15]
Sorted array uisng insretion sort : [6, 15, 25, 27, 53, 74, 87, 91, 94]
Before Sorting : [71, 5, 60, 19, 4, 78, 42]
After Sorting : [4, 5, 19, 42, 60, 71, 78]
String array before sorting : [London, Paris, Tokyo, NewYork, Chicago]
String array after sorting : [Chicago, London, NewYork, Paris, Tokyo]

Another useful thing to learn from this example is how to generate Random numbers in Java. You can see that our getRandomArray(int length) method creates a random array of a given length.

This uses the static utility method Math.random() which returns a double value between 0.0 to 0.1, if you need to convert it to an integer, in the range of 0 to 99, you need to multiply it with 100. After that, you can cast it to int to get rid of decimals.

That's all about the Insertion sort in Java. It's one of the really beautiful algorithms and works best for the already sorted list. It has lots of practical uses but has limitations also. You should not use Insertion sort for sorting a big list of numbers, as its best-case performance is in order of O(n), which can be very high for a list of say 1 million integers.

To short those lists, you need sorting algorithms that have logarithmic complexity e.g. quicksort, mergesort, or heapsort, which provides the best-case complexity of O(nLogn), because log reduces the power of 10^n into n like 1 million will become 10^6 means 6.

In order to remember the Insertion sort algorithm, just remember how you sort your hand in poker or any card game. If that is tough, just remember how you arrange your shirts in the wardrobe.


Other array-based coding problems for Interviews:

• How to implement a quicksort algorithm without recursion in Java? (solution)
• How to remove an element from an array in Java? (solution)
• 20 Sorting algorithms questions for coding interviews (questions)
• Difference between Quicksort and Counting Sort Algorithm? (answer)
• Top 10 Data Structure and Algorithms Courses for Java Programmers (courses)
• How to find duplicates from an unsorted array in Java? (solution)
• Difference between Counting Sort and Bucket Sort Algorithm? (answer)
• How to find all pairs in an array whose sum is equal to k (solution)
• How to remove duplicates from an array in Java? (solution)
• How to find a missing value from an array containing 1 to 100? (solution)
• 50+ Data Structure and Algorithms Problems from Interviews (questions)
• Difference between Quicksort and Mergesort Algorithm? (answer)
• Some Free courses to learn data Structure in-depth (FreeCodeCamp)
• How to reverse an array in place in Java? (solution)
• How to count the number of leaf nodes in a given binary tree in Java? (solution)
• Recursive InOrder traversal Algorithm (solution)
• 10 Free Data Structure and Algorithm Courses for Programmers (courses)
• 100+ Data Structure Coding Problems from Interviews (questions)

Thanks for reading this article so far. If you like this Java Array tutorial then please share it with your friends and colleagues. If you have any questions or feedback then please drop a comment.

P. S. - If you are looking for some Free Algorithms courses to improve your understanding of Data Structure and Algorithms, then you should also check these free data structure courses on Udemy and Coursera to learn better.