Insertion Sort Algorithm in Java with Program Example

What is Insertion Sort Algorithm?

Insertion sort is a simple sorting algorithm suited for small data sets. During each iteration, the algorithm:

• Removes an element from an array.
• Compares it against the largest value in the array.
• Moves the element to its correct location.

The behaviour mirrors the way a card player arranges a hand: each new card is picked up and pushed left past every larger card until it rests in the right spot. Because all shifting happens inside the original array, insertion sort is both in-place and stable.

It belongs to the same family of beginner-friendly Java sorting routines as bubble sort, yet it normally performs far fewer writes on data that is already partly ordered.

Insertion Sort Algorithm Process

Here is how the Insertion sort algorithm process works graphically:

The animation repeats the same three steps the Java program below performs. The dry-run table traces those steps on the sample array {860, 8, 200, 9}, exactly as the program prints them at run time.

Notice that pass 3 needs two comparisons because the key 9 has to travel past two larger values. The number of comparisons therefore grows with how far out of order each element starts.

Java Program Example to Sort an Array using Insertion Sort Algorithm:

The program below sorts the array {860, 8, 200, 9} and prints a running commentary, so every comparison and every shift is visible. Save it as InsertionSortExample.java and compile it with any JDK 8 or later release.

package com.guru99;
 
public class InsertionSortExample {
 
	
    public static void main(String a[])
    {    
        int[] myArray  = {860,8,200,9};  
        
        System.out.println("Before Insertion Sort");  
        
        printArray(myArray);
            
        insertionSort(myArray);//sorting array using insertion sort    
           
        System.out.println("After Insertion Sort");  
        
        printArray(myArray);   
    }    
 public static void insertionSort(int arr[]) 
	{  
        int n = arr.length;  
        
        for (int i = 1; i < n; i++)
        {   System.out.println("Sort Pass Number "+(i));
            int key = arr[i];  
            int j = i-1;  
            
            while ( (j > -1) && ( arr [j] > key ) ) 
            {  
            System.out.println("Comparing "+ key  + " and " + arr [j]); 
                arr [j+1] = arr [j];  
                j--;  
            }  
            arr[j+1] = key; 
            System.out.println("Swapping Elements: New Array After Swap");
            printArray(arr);
        }  
    }
 static void printArray(int[] array){
	    
	    for(int i=0; i < array.length; i++)
		{  
			System.out.print(array[i] + " ");  
		} 
	    System.out.println();
	    
	}
}

Running the class produces the trace shown here. Each Sort Pass Number line marks one iteration of the outer loop, and the line printed after each swap shows the array as it stands at that moment.

Code Output:

Before Insertion Sort
860 8 200 9 
Sort Pass Number 1
Comparing 8 and 860
Swapping Elements: New Array After Swap
8 860 200 9 
Sort Pass Number 2
Comparing 200 and 860
Swapping Elements: New Array After Swap
8 200 860 9 
Sort Pass Number 3
Comparing 9 and 860
Comparing 9 and 200
Swapping Elements: New Array After Swap
8 9 200 860 
After Insertion Sort
8 9 200 860

Time and Space Complexity of Insertion Sort

Insertion sort performance depends heavily on how ordered the input already is, which is why the best case and the worst case differ by a whole order of growth.

Space usage is far simpler. Only the counters i, j, n and key are created, and the array is rearranged in place, so auxiliary space is O(1) no matter how large the input grows.

Because the inner loop stops as soon as it meets a smaller value, insertion sort is described as adaptive: the closer the input is to sorted order, the closer the running time moves towards linear.

Advantages and Disadvantages of Insertion Sort

Insertion sort survives in production libraries despite its quadratic average case, because its constant factors are tiny and its behaviour is predictable.

Advantages

• Simple to write and easy to trace by hand, which suits it to teaching and to interviews.
• Stable, so records that share a key keep their original relative order.
• In-place, needing only O(1) extra memory beyond the input array.
• Adaptive, reaching O(n) on data that is already nearly sorted.
• Online, meaning it can sort a list while new elements are still arriving.

Disadvantages

• Quadratic time on random or reverse-ordered input makes it unsuitable for large arrays.
• Each shift writes to the array, so it moves more data than selection sort does.
• Merge sort and quicksort outperform it comfortably once the input passes a few dozen elements.

A practical rule is to reach for insertion sort when the array is small, when the data is almost in order, or when a divide-and-conquer sort has reduced a partition to a handful of elements.

Insertion Sort vs Bubble Sort vs Selection Sort

All three algorithms are quadratic comparison sorts, yet they differ in stability, in how they react to ordered input, and in the number of writes they perform.

Selection sort wins when a write is expensive, because it performs the fewest swaps. Insertion sort wins almost everywhere else at this scale, especially on partially ordered data, which is why library sorts such as the one behind common Java exercises and the JDK internals switch to it for very small partitions.

FAQs