Insertion Sort in Java: Explained with Examples

Basics of Sorting Algorithms in Java:

Sorting refers to the arrangement of elements in a specific order, often used in data structures such as arrays. The criteria in which the elements are sequenced is diverse. The most common ones are the sorting of numbers in ascending and descending order, lexicographical sorting of strings etc. Some of the most common and effective sorting algorithms used in Java and other object-oriented programming languages are:

• Bubble sort
• Selection sort
• Insertion sort
• Merge sort
• Quicksort
• Heapsort

Insertion sort is an easy-to-understand sorting algorithm whose working is similar to the manner we play cards. The input array list is split into two parts: sorted and unsorted. The splitting is virtual. The items from the unsorted part of the list are shifted to the sorted portion one at a time in each iteration.

Learn Software Development Courses online from the World’s top Universities. Earn Executive PG Programs, Advanced Certificate Programs or Masters Programs to fast-track your career.

Implementation of Insertion Sort in Java

In insertion sort, the current element is compared with the immediate next element in each pass. The comparison is made to determine if the element is greater than the element it is compared to. If the item is greater than the one it is compared to, it is retained in the same position and the iteration continues. If the item is lesser than the one it is compared to, it is shifted to its appropriate position by shifting the larger items by one position backwards.

An example for Insertion Sort

Figure 1 Insertion Sort Example

In the insertion sorting algorithm, the first iteration starts with an assumption that the item at the 0th position is already sorted. For each iteration, the current item is checked against the items in the sorted region of the list. The items that are greater during the comparison are moved towards the right of the list. In this algorithm, the current item can be inserted when the smaller item is reached.

Explore our Popular Software Engineering Courses

Figure 1 shows an example of an insertion sort with a list of items. In the first iteration, the element [54] is assumed to be sorted already. This acts as a reference for the comparison during the first iteration. The second element [26] is less than 54 and hence, 54 is moved to the right. 

Check out our free technology courses to get an edge over the competition.

Example Java Code for an Insertion Sort:

Now that we have gained knowledge about the working of the insertion sort algorithm let’s visualize how a Java code is written to sort the elements with this algorithm. In the example code shown below, the values of arr can be changed as per your needs and how the program responds for different input arrays. 

The output of the above code is mentioned below.

Explanation of the implemented Java code:

• As an initial step in the program, a method to accept the input array to be sorted is created. It is referred to as sort_arr in the above code.
• Secondly, an outer for loop is created to iterate over each element of the input array, as reflected in line 5 of the above code.
• The next step is the creation of a distinct iterator ‘j’ to evaluate for the sorting of the elements in ascending order of the input list. This is shown in the 7th line of the code.
• In the next step, an inner while loop is created.
  • The while loop is expected to meet two specified conditions as in line 9 of the code. The two conditions are that the j’s value must be more than 0 and the j-1 index value must be more than the j’s index value. 
  • If both the conditions evaluate to true, lines 11 to 14 are executed and the j’s index value is assigned as the key’s value. 
  • The values at j-1 and j are exchanged. 
  • j’s value decrements by 1 and the loop repeats till any of the two conditions is evaluated to be false. 
• The execution continues for each traverse of the outer for loop till the condition for that also breaks. 

In-Demand Software Development Skills

Check out upGrad’s Advanced Certification in DevOps 

Advantages of Insertion sort in Java

• Insertion sort in Java is a purely simple sorting algorithm.

• There is no change in the comparative order of constituents of the list.

• This sorting algorithm is able to sort the list as and when the list is received.

• This sorting algorithm works effectively for small datasets.

• The algorithm demands a constant quantity of extra space or memory. 

Read our Popular Articles related to Software Development

Performance of Insertion Sort

• Time complexity and space complexity of insertion sort are O (n2) and O (1), respectively.
• (n2) assessments and switches are the worst-case performance of this sorting algorithm.
• (n) comparisons and O (1) exchanges are the best-case performance of insertion sort.
• The average case performance is also with O (n2) swaps and comparisons.

Demerits of Insertion Sort

• The performance of insertion sort is not as good as other sorting algorithms.

• This sorting algorithm is not suitable for huge lists because the number of steps required to sort the list is the square of the number of items in the list.

At upGrad, we understand the importance of practical, hands-on learning – especially when it comes to software development. As a result, our courses and training initiatives have practicality at their very core. One such initiative is Full Stack Development Bootcamp which will help you develop all the relevant skills required to excel in full-stack development. 

Plan your Software Development Career Now!

Apply For Master of Science in Computer Science