Sorting is important in programming. It helps organize data. Sorting improves performance in searching, analysis, and reporting. There are many sorting algorithms. One of the simplest is Insertion Sort.

In this article, we will learn how to implement Insertion Sort in Java. We will explain each step in simple words. You will see examples and understand how it works.

What Is Insertion Sort?

Insertion Sort is a simple sorting algorithm. It works like how you sort playing cards. You take one card at a time and place it in the right position. It compares the current element with those before it. If needed, it shifts elements to the right. Then, it inserts the current element at the correct place.

How Insertion Sort Works

Let’s understand with a small list:

Example List: [8, 3, 5, 1]

Steps:

1. First element (8) is already sorted.
2. Compare 3 with 8. Move 8 right. Insert 3 before it → [3, 8, 5, 1]
3. Compare 5 with 8. Move 8 right. Insert 5 after 3 → [3, 5, 8, 1]
4. Compare 1 with 8, 5, 3. Move them right. Insert 1 at start → [1, 3, 5, 8]

Now the list is sorted!

Why Use Insertion Sort?

Insertion Sort is simple and easy to code. It works well for:

• Small datasets
• Nearly sorted lists
• Educational purposes and practice

However, it is not good for large datasets. It has a time complexity of O(n²).

Time Complexity of Insertion Sort

• Best Case (already sorted): O(n)
• Average Case: O(n²)
• Worst Case (reversed list): O(n²)

It performs fewer steps in nearly sorted data.

How to Implement Insertion Sort in Java

Now let’s write the code for Insertion Sort in Java. We will explain each part.

Step 1: Define a Class

javaCopyEditpublic class InsertionSortExample {
    // Code goes here
}

We create a class named InsertionSortExample.

Step 2: Create the Sorting Method

javaCopyEditpublic static void insertionSort(int[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

Let’s break it down:

• arr[i] is the current value (called key).
• j starts from the previous index.
• While arr[j] > key, shift arr[j] to the right.
• Insert the key at the correct position.

This logic sorts the array step by step.

Step 3: Create the Main Method

Now we test the code.

javaCopyEditpublic static void main(String[] args) {
    int[] numbers = {9, 5, 1, 4, 3};

    System.out.println("Before sorting:");
    printArray(numbers);

    insertionSort(numbers);

    System.out.println("After sorting:");
    printArray(numbers);
}

This method:

• Creates an array of numbers
• Prints the array before sorting
• Calls the sort method
• Prints the array after sorting

Step 4: Print the Array

Let’s add a helper method to print the array.

javaCopyEditpublic static void printArray(int[] arr) {
    for (int number : arr) {
        System.out.print(number + " ");
    }
    System.out.println();
}

Now you can see how the array changes before and after sorting.

Full Code Example

javaCopyEditpublic class InsertionSortExample {

    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;

            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }

    public static void printArray(int[] arr) {
        for (int number : arr) {
            System.out.print(number + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] numbers = {9, 5, 1, 4, 3};

        System.out.println("Before sorting:");
        printArray(numbers);

        insertionSort(numbers);

        System.out.println("After sorting:");
        printArray(numbers);
    }
}

Sample Output

yamlCopyEditBefore sorting:
9 5 1 4 3 
After sorting:
1 3 4 5 9 

This confirms that the sorting works correctly.

Advantages of Insertion Sort in Java

• Easy to implement
• Works well with small inputs
• Stable sort (keeps equal items in order)
• Good for educational use

When Not to Use Insertion Sort

Avoid Insertion Sort when:

• The dataset is large
• Performance is critical
• Better algorithms like Merge Sort or Quick Sort are available

Real-World Uses

• Sorting small records in a database
• Teaching algorithm basics
• Handling partially sorted arrays

Even though it is not the fastest, it is useful in many simple tasks.

Final Tips

• Practice with different inputs
• Add print statements to see how it works
• Try sorting strings or objects
• Use Java’s built-in sort methods for large arrays

Conclusion

Insertion Sort in Java is a great way to learn sorting. It is simple and easy to understand. In this guide, we showed how to implement it step-by-step. We covered the logic, code, and output. We also explained when to use it. Now you can try it yourself. Understanding sorting helps in coding interviews and software development. Keep practicing and exploring other sorting methods too. The more you practice, the better you understand algorithms.