How Insertion Sort Works: Step‑by‑Step Visual Guide and Java Implementation

Card Sorting Example

People often wonder how to sort playing cards. Suppose you have the hearts 6, 7, 9, 10 already in ascending order. When you draw an 8, the most natural way is to insert it between 7 and 9, keeping the hand sorted.

Below is the visual representation of inserting the 8 into the ordered hand.

Insertion Sort Process

Insertion sort treats the first element of an array as a sorted sub‑array and then inserts each subsequent element into its correct position by shifting larger elements to the right.

First round : Compare element 8 with the sorted element 5. Since 8 > 5, no swap is needed and the sorted region now contains two elements.

Second round : Compare element 6 with the sorted elements. 6 < 8, so swap 6 and 8; then 6 > 5, so no further swap. The sorted region now has three elements.

Third round : Insert element 3. It is smaller than 8, 6, and 5, so it is shifted left step by step until it reaches the first position.

The process repeats for each remaining element, resulting in a total of (array length - 1) rounds.

Optimized Insertion (Shift‑Instead‑Swap)

Instead of swapping each time, the algorithm can temporarily store the element to be inserted, shift larger elements one position to the right, and finally place the stored element into the vacant spot, reducing the number of assignments.

Java Implementation

<code>public static void sort(int[] array) {
    for (int i = 1; i < array.length; i++) {
        int insertValue = array[i];
        int j = i - 1;
        // Shift elements to the right while they are larger than insertValue
        for (; j >= 0 && insertValue < array[j]; j--) {
            array[j + 1] = array[j];
        }
        // Insert the stored value into its correct position
        array[j + 1] = insertValue;
    }
}

public static void main(String[] args) {
    int[] array = {12, 1, 3, 46, 5, 0, -3, 12, 35, 16};
    sort(array);
    System.out.println(java.util.Arrays.toString(array));
}
</code>

This code follows the optimized insertion‑sort logic: it iterates over the array, stores the current element, shifts larger elements to the right, and finally writes the stored element into its correct position.