Insertion Sort in Java: A How-To Guide

A Java insertion sort evaluates each item in a list. If an item is less than the one before, the sort swaps the items. Otherwise, the items stay in the same place and the next two items are compared in the list.

Computers are good at sorting lists of items. Using loops, you can search through all the items in a list and change their order until they appear a certain way.

In programming, there are a few standard methods of sorting lists. We call these sort algorithms. Sort algorithms read through all the items in a list and sort them using a particular set of instructions. One of the most common sort algorithms you’ll encounter is an insertion sort.

In this guide, we’re going to discuss how to implement a Java insertion sort algorithm. We’ll walk through an example along the way so that you can learn how the logic behind this sort works.

Let’s get started!

What is a Java Insertion Sort?

A Java insertion sort works similar to sorting cards in your hand in a card game. Insertion sorts check each item in a list and swaps them with an item to its left. Whether an item is swapped depends on if the item is greater than or less than previous items.

Imagine, for a moment, that you are playing a card game – whist, rummy, whatever. When you’re sorting your cards, what do you do?

You will start at the left and check whether the second card is sorted. If that card is greater than the last, it should remain in the same position. Oherwise, it should move up a position in the list.

You’ll go through every card in your hand and perform this operation until every card appears in its right order.

When Should You Use an Insertion Sort?

Insertion sorts are most used when there are only a few elements to the left that need to be sorted.

There are more efficient algorithms that you can use to sort large lists of data, such as a merge sort. This is why you shouldn’t always default to using an insertion sort. With that said, insertion sorts are more efficient than bubble sorts and selection sorts at sorting elements in a list.

An insertion sort is a simple sorting algorithm which means it is good for beginners to learn.

Insertion Sort Walkthrough

Visualizing a deck of cards isn’t the most intuitive in the world. Let’s walk through a programming example to get you started. Consider the following list:

In this list, we assume the first element is sorted.

Our next step is to compare the second item in our list with the first one. If the first item is greater than the second item, then that item is placed in front of the first item.

In this case, 6 is greater than 8. This means that 6 will move back in our list by one position, and 8 will move forward by one position:

Now we need to compare the third element with the elements to its left: Is 3 greater than 8? No, so 8 moves position to the right:

Is 3 greater than 6? No, so we move the number 6:

Now, we’ve got to compare whether the fourth item in our list – the last item – is greater than every other item in our list. In this case, 9 is greater than all the items that come before it: 8, 6, and 3.

Here’s the algorithm that we have used to sort our list:

• The first element is sorted.
• Compare the second item to the item on its left.
• If this item is greater than the value to its left, the item stays in the same place. Otherwise, we move the value to the left.
• Repeat until all items appear in order.

We now have a sorted array. Insertion sorts sort through one item at a time. Let’s discuss how to implement this sorting algorithm in Java.

How to Perform an Insertion Sort in Java

The highest value of two values that are being compared is inserted one position to the right every time the sort function is run.

It’s all well talking about this in theoretical terms, but how do you implement it in Java? That’s a good question. Let’s write a class that performs an insertion sort on a list of student grades.

Prepare the Arrays Library

Let’s start by importing the Arrays library into our Java program. We’ll use this library to print our list to the console once we have sorted it:

import java.util.Arrays;

Declare a Sort Method

We’ll start by declaring a method that goes through our list and sorts our data in ascending order:

class SortGrades {
public static void insertionSort(int [] numbersToSort) {
	int itemCount = numbersToSort.length;

	for (int value = 1; value < itemCount; value++) {
		int key = numbersToSort[value];
		int last = value - 1;

		while (last >= 0 && key < numbersToSort[last]) {
			numbersToSort[last + 1] = numbersToSort[last];
			--last;
		}

		numbersToSort[last + 1] = key;
	}
}
}

We start by finding out how many items in our input array. This allows us to create a loop that goes through every item in our list. We initialize a for loop which loops until we sort our list.

Within our for loop, we have declared two variables: key and last.

"Career Karma entered my life when I needed it most and quickly helped me match with a bootcamp. Two months after graduating, I found my dream job that aligned with my values and goals in life!"

Venus, Software Engineer at Rockbot

Find Your Bootcamp Match

The “key” Java variable tracks which item we are currently sorting. The “last” variable tracks how many items have to be sorted on the left of the item.

Our program will compare the value of “key” with each element on its left until we find a smaller element. This happens in our Java “while” loop.

Define a Main Function

When we run this code, nothing happens. That’s because we have not yet defined our main function. Let’s define a main function which defines an int array (an array of numbers). This main function uses the insertionSort() function we’ve declared to sort those numbers. Paste in this code after declaring your insertionSort Java method:

public static void main(String args[]) {
	int[] numbers = { 8, 6, 3, 9 };
	InsertionSort sortNumbers = new InsertionSort();
	sortNumbers.insertionSort(numbers);

	String arrayToString = Arrays.toString(numbers);
	System.out.println("Sorted list: " + arrayToString);
}

In our main method, we have declared a list of numbers that we want to sort. We’ve created an instance of our InsertionSort() method called sortNumbers. We use this method to sort our list of numbers in ascending order. This method changes the values inside our “numbers” array; we haven’t declared a separate array to store its values.

Next, we have used the Arrays.toString() method to convert our numbers array to a string. We print out the sorted list to the console.

Complexity Review

The insertion sort has an average case complexity of O(n^2). This happens when the no elements are sorted.

The best case complexity happens if an array is sorted. This will yield a time complexity of O(n). This is because the inner loop in an insertion sort will not run at all in this case.

In the worst case, an insertion sort performs at O(n^2). This happens if an array is in ascending or descending order and you want to sort it inversely (i.e. ascending to descending). This would involve comparing every element with all the other elements.

Conclusion

Insertion sorts are an efficient method of sorting data. Insertion sorts compare values starting with the second in a list. If this value is greater than the one to the left of it, our list does not change. Otherwise, the value is moved until the item to its left is less than it.

Now you’re ready to start writing your own insertion sort algorithm in Java! If you’re looking for more Java learning resources, check out our How to Learn Java guide.