Sorting is one of the most common operations in computer science, and there are multiple algorithms to get it done. One of the simplest yet effective methods is Insertion Sort. While it may not be the fastest for very large datasets, it shines for smaller inputs and situations where data is nearly sorted.

In this guide, we’ll break down Insertion Sort in Java, covering the algorithm step by step, sharing clean code examples, and explaining its time and space complexity.

What Is Insertion Sort?

Insertion Sort is a comparison-based sorting algorithm that works much like sorting a hand of playing cards.

• You start with the first card (element) in your hand — that’s already sorted.
• Then you pick the next card and insert it into the correct place among the already sorted cards.
• You repeat this until all cards are in order.

The algorithm builds the final sorted array one element at a time.

How Insertion Sort Works

Here’s the process in simple steps:

1. Assume the first element is already sorted.
2. Take the next element (called the “key”).
3. Compare the key with the elements in the sorted portion.
4. Shift larger elements one position to the right.
5. Insert the key into the correct position.
6. Repeat until the entire array is sorted.

Example

Let’s say we have an array:

[7, 3, 5, 2]

• Start with 7 → sorted list is [7].
• Next element is 3 → compare with 7 → insert before 7 → [3, 7].
• Next element is 5 → compare with 7 → insert between 3 and 7 → [3, 5, 7].
• Next element is 2 → move 7, 5, 3 to the right → insert 2 at the start → [2, 3, 5, 7].

Sorted..!

Java Code for Insertion Sort

Here’s a simple Java implementation:

public class InsertionSortExample {
    
    // Method to perform insertion sort
    public static void insertionSort(int[] arr) {
        int n = arr.length;

        for (int i = 1; i < n; i++) {
            int key = arr[i];   // The element to insert
            int j = i - 1;

            // Shift elements of arr[0..i-1] that are greater than key
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }

            // Place key at its correct position
            arr[j + 1] = key;
        }
    }

    // Main method to test
    public static void main(String[] args) {
        int[] numbers = {7, 3, 5, 2, 9, 1};

        System.out.println("Before Sorting:");
        for (int num : numbers) {
            System.out.print(num + " ");
        }

        insertionSort(numbers);

        System.out.println("\nAfter Sorting:");
        for (int num : numbers) {
            System.out.print(num + " ");
        }
    }
}

• Outer loop (for): Goes through each element in the array starting from index 1 (since the first element is considered sorted).
• Key: The element we want to insert into the sorted part.
• Inner loop (while): Shifts elements greater than the key to the right.
• Insertion step: Places the key into the correct spot.

This way, the array gradually becomes sorted after each iteration.

Time Complexity of Insertion Sort

• Best Case (Already Sorted Array):
   Only one comparison per element → O(n).
• Worst Case (Reverse Sorted Array):
   Every element needs to be compared and shifted → O(n²).
• Average Case:
   On average, about half the elements are compared → O(n²).

Space Complexity

Insertion Sort is an in-place algorithm, meaning it doesn’t need extra space apart from a few variables → O(1) space complexity.

When to Use Insertion Sort in Java

Insertion Sort works best when:

• You’re dealing with small datasets.
• The data is already nearly sorted.
• You want a simple, easy-to-implement algorithm.

In real-world Java applications, more advanced algorithms like Merge Sort or Quick Sort are preferred for large datasets, but Insertion Sort is great for learning and small-scale sorting.

Conclusion

Insertion Sort in Java is a simple yet powerful way to understand sorting. It’s not the fastest for huge datasets, but it’s perfect for teaching, smaller inputs, or partially sorted data. By mastering this algorithm, you’ll strengthen your foundation for more advanced sorting techniques.

If you’re learning Java, practicing insertion sort will give you a deeper appreciation for how sorting works under the hood.