Insertion Sort Algorithm in Java: A Clear Example & Step‑by‑Step Guide

What is Insertion Sort Algorithm?

Insertion sort is a straightforward sorting technique ideal for small or nearly sorted data sets. In each iteration, the algorithm removes an element, compares it with the preceding elements, and places it in its proper position.

Insertion sort operates in O(n²) time in the worst and average cases but achieves linear performance when the array is already sorted. It is an in‑place, stable sort that requires only constant extra space.

Insertion Sort Algorithm Process

Here is a visual representation of the insertion sort workflow:

Insertion Sort Algorithm Process

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

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();
    }
}

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