Java Program for Insertion Sort with Example and Explanation

A Java program for insertion sort uses nested loops to pick each element and insert it into its correct position in the sorted part of the array, like for (int i = 1; i < arr.length; i++) { int key = arr[i]; int j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; }.

Examples

Inputarr = {5, 2, 9, 1, 5}

OutputSorted array: 1 2 5 5 9

Inputarr = {1, 2, 3, 4, 5}

OutputSorted array: 1 2 3 4 5

Inputarr = {10}

OutputSorted array: 10

How to Think About It

To sort an array using insertion sort, think of dividing the array into a sorted part and an unsorted part. Start from the second element, compare it with elements before it, and insert it into the correct position by shifting larger elements one step right. Repeat this for each element until the whole array is sorted.

Algorithm

1

Start from the second element of the array (index 1).

2

Store the current element as the key.

3

Compare the key with elements before it in the sorted part.

4

Shift all elements larger than the key one position to the right.

5

Insert the key into the correct position.

6

Repeat for all elements until the array is sorted.

Code

java

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 9, 1, 5};
        insertionSort(arr);
        System.out.print("Sorted array: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

Output

Sorted array: 1 2 5 5 9 

Dry Run

Let's trace the array {5, 2, 9, 1, 5} through the insertion sort code.

1

Start with i=1, key=2

Compare 2 with 5; since 5 > 2, shift 5 right. Insert 2 at position 0. Array becomes {2, 5, 9, 1, 5}.

2

i=2, key=9

Compare 9 with 5; 5 < 9, no shift needed. Insert 9 at position 2. Array unchanged {2, 5, 9, 1, 5}.

3

i=3, key=1

Compare 1 with 9, 5, 2; all greater than 1, shift them right. Insert 1 at position 0. Array becomes {1, 2, 5, 9, 5}.

4

i=4, key=5

Compare 5 with 9; 9 > 5, shift 9 right. Insert 5 at position 3. Array becomes {1, 2, 5, 5, 9}.

Iteration	Array State
i=1	2 5 9 1 5
i=2	2 5 9 1 5
i=3	1 2 5 9 5
i=4	1 2 5 5 9

Why This Works

Step 1: Picking the key element

The code selects the element at index i as the key to insert into the sorted part.

Step 2: Shifting elements

Elements larger than the key are shifted right to make space for the key.

Step 3: Inserting the key

The key is placed in its correct position, ensuring the sorted part remains ordered.

Alternative Approaches

Recursive Insertion Sort

java

public class RecursiveInsertionSort {
    public static void insertionSort(int[] arr, int n) {
        if (n <= 1) return;
        insertionSort(arr, n - 1);
        int key = arr[n - 1];
        int j = n - 2;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 9, 1, 5};
        insertionSort(arr, arr.length);
        System.out.print("Sorted array: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

Uses recursion instead of loops; easier to understand for some but less efficient due to call overhead.

Using Java's Arrays.sort()

java

import java.util.Arrays;
public class BuiltInSort {
    public static void main(String[] args) {
        int[] arr = {5, 2, 9, 1, 5};
        Arrays.sort(arr);
        System.out.print("Sorted array: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

Built-in method is highly optimized and simple but does not teach the insertion sort algorithm.

Complexity: O(n^2) time, O(1) space

Time Complexity

Insertion sort uses nested loops; in the worst case, each element is compared with all previous elements, leading to O(n^2) time.

Space Complexity

It sorts the array in place without extra arrays, so space complexity is O(1).

Which Approach is Fastest?

Built-in sort methods are faster for large data, but insertion sort is simple and efficient for small or nearly sorted arrays.

Approach	Time	Space	Best For
Insertion Sort	O(n^2)	O(1)	Small or nearly sorted arrays
Recursive Insertion Sort	O(n^2)	O(n) due to recursion stack	Learning recursion
Java Arrays.sort()	O(n log n)	O(n) or O(1) depending on implementation	Large arrays, production use