Implementing the Insertion Sort Algorithm in Java

Insertion Sort is a simple and intuitive sorting algorithm. Its core idea is similar to how we organize a deck of cards: we insert unsorted elements one by one into their correct positions in the sorted portion, gradually building the entire sorted array. This algorithm is suitable for sorting small datasets and is relatively easy to understand.

Basic Idea¶

Imagine you have a shuffled deck of cards. You would insert each card into its correct position one by one:
1. Start with the second card (assuming the first card is already sorted), and mark the current card as the “element to insert.”
2. Compare the element to insert with the cards in the sorted portion from right to left:
- If a card in the sorted portion is larger than the element to insert, shift that card one position to the right.
- Repeat this until you find a card smaller than the element to insert or reach the leftmost position.
3. Insert the element into this position, increasing the length of the sorted portion by 1.
4. Repeat steps 1-3 until all cards are inserted.

Java Code Implementation¶

Here is the complete Java code for insertion sort with detailed comments:

public class InsertionSort {

    // Insertion sort method
    public static void insertionSort(int[] arr) {
        // If the array is empty or has only one element, it is already sorted
        if (arr == null || arr.length <= 1) {
            return;
        }

        // Start from the second element (index 1) and insert into the sorted portion
        for (int i = 1; i < arr.length; i++) {
            // Save the current element to be inserted
            int current = arr[i];
            // j represents the index of the last element in the sorted portion, initially i-1
            int j = i - 1;

            // Compare elements in the sorted portion; shift larger elements right
            // Termination condition: j >= 0 and arr[j] > current
            while (j >= 0 && arr[j] > current) {
                arr[j + 1] = arr[j]; // Shift the larger element right by one position
                j--; // Move left to compare the next element
            }

            // Insert the current element into the correct position
            arr[j + 1] = current;
        }
    }

    // Test method: Verify if the sorting is correct
    public static void main(String[] args) {
        int[] arr = {5, 2, 4, 6, 1, 3};
        System.out.println("Before sorting: " + java.util.Arrays.toString(arr));

        insertionSort(arr);

        System.out.println("After sorting: " + java.util.Arrays.toString(arr));
    }
}

Code Execution Process Analysis¶

Taking the array {5, 2, 4, 6, 1, 3} as an example, the insertion sort process is demonstrated step by step:

Initial Array: `[5, 2, 4, 6, 1, 3]`¶

Round 1 (i=1, current=2):¶

Sorted portion: [5]
Comparison: arr[0] = 5 > 2 → shift 5 to arr[1], j becomes -1
Insertion position: arr[0] = 2
Result: [2, 5, 4, 6, 1, 3]

Round 2 (i=2, current=4):¶

Sorted portion: [2, 5]
Comparison: arr[1] = 5 > 4 → shift 5 to arr[2], j=0
Comparison: arr[0] = 2 <= 4 → stop looping
Insertion position: arr[1] = 4
Result: [2, 4, 5, 6, 1, 3]

Round 3 (i=3, current=6):¶

Sorted portion: [2, 4, 5]
Comparison: arr[2] = 5 <= 6 → no shift needed
Insertion position: arr[3] = 6
Result: [2, 4, 5, 6, 1, 3] (array unchanged)

Round 4 (i=4, current=1):¶

Sorted portion: [2, 4, 5, 6]
Comparison: arr[3] = 6 > 1 → shift 6 to arr[4], j=2
Comparison: arr[2] = 5 > 1 → shift 5 to arr[3], j=1
Comparison: arr[1] = 4 > 1 → shift 4 to arr[2], j=0
Comparison: arr[0] = 2 > 1 → shift 2 to arr[1], j=-1
Insertion position: arr[0] = 1
Result: [1, 2, 4, 5, 6, 3]

Round 5 (i=5, current=3):¶

Sorted portion: [1, 2, 4, 5, 6]
Comparison: arr[4] = 6 > 3 → shift 6 to arr[5], j=3
Comparison: arr[3] = 5 > 3 → shift 5 to arr[4], j=2
Comparison: arr[2] = 4 > 3 → shift 4 to arr[3], j=1
Comparison: arr[1] = 2 <= 3 → stop looping
Insertion position: arr[2] = 3
Final Result: [1, 2, 3, 4, 5, 6]

Algorithm Characteristics Summary¶

Time Complexity:
- Best case (array already sorted): O(n) (only n-1 comparisons needed)
- Worst case (array reversed): O(n²) (n-1 inner loops, each with n comparisons)
- Average case: O(n²)
Space Complexity: O(1) (in-place sorting, only one temporary variable for the element to insert)
Stability: Stable sort (relative order of equal elements remains unchanged)
Applicable Scenarios: Suitable for small datasets or nearly sorted data, as the O(n²) time complexity has a smaller impact on small data sizes.

Conclusion¶

The core of insertion sort is “gradual insertion.” By comparing elements with the sorted portion and shifting them, we ultimately build the sorted array. When implementing in Java, it is important to save the element to be inserted (to avoid overwriting) and handle boundary conditions correctly (e.g., the termination condition for j). Although insertion sort has a high time complexity, its simple implementation, stability, and in-place nature make it perform well for small-scale data sorting.