Insertion Sort in Java

Why Use Insertion Sort?

1. Efficient for Small Data Sets

Insertion Sort shines when dealing with small datasets or nearly sorted arrays. Unlike more complex algorithms like Quick Sort or Merge Sort, which involve recursive calls and extra memory, Insertion Sort works in-place and has very low overhead. For arrays with less than 20–30 elements, it often outperforms faster algorithms in real-world scenarios due to reduced overhead.

For example, consider a partially sorted array of exam scores:

int[] scores = {65, 67, 68, 70, 85, 80}; // Just one value out of place 

Insertion Sort can efficiently correct the order with minimal comparisons and shifts.

This makes it highly effective in Java applications like small utility modules, form validations, or processing temporary lists where data is already mostly sorted. Its predictable performance in such cases often outweighs the theoretical speed of more complex algorithms.

2. Simple to Implement and Understand

Insertion Sort is a go-to algorithm for beginners due to its clear logic and easy implementation. The concept mirrors how people sort playing cards in their hands—by picking one card at a time and placing it in the correct position among the already sorted cards.

For example:

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;
}

This simple structure makes Insertion Sort ideal for teaching fundamental sorting logic in Java. It’s often used in Java programming project examples where clarity and educational value take precedence over raw performance, such as academic tools, basic GUIs, or learning platforms.

3. Stable Sorting Algorithm

Insertion Sort is a stable sorting algorithm, meaning it preserves the relative order of elements with equal values. This is especially important when sorting records with multiple fields.

Imagine sorting a list of employees by department ID, but several employees belong to the same department. A stable sort keeps their original order—critical if a secondary sort (like by name) was previously applied.

For example:

class Employee {
    String name;
    int departmentId;
}
// Insertion Sort keeps "John" before "Lisa" if they share the same departmentId.

Working of Insertion Sort Algorithm

The insertion sort algorithm follows an interesting approach to sorting elements in an array. Let's understand the step-by-step working of the algorithm:

1. Start with the first element of the array & consider it as already sorted.
 

2. Move to the next element, which becomes the "key" element. Compare the key element with the elements in the sorted portion of the array, starting from right to left.
 

3. If an element in the sorted portion is greater than the key element, shift that element one position to the right. Continue shifting elements until you find an element smaller than or equal to the key element or reach the beginning of the array.
 

4. Insert the key element into the correct position within the sorted portion of the array, which is the position where the shifting stopped.
 

5. Repeat steps 2-4 for all the remaining unsorted elements until the entire array is sorted.
 

At each iteration, the algorithm maintains two subarrays:
 

- The sorted subarray, which contains the elements that have been inserted into their correct positions.
 

- The unsorted subarray, which contains the remaining elements that need to be processed.

As the algorithm progresses, the sorted subarray grows, & the unsorted subarray shrinks until all elements are inserted into their proper positions, resulting in a fully sorted array.

Note: The insertion sort algorithm performs in-place sorting, which means it modifies the original array without requiring additional storage space. It efficiently handles small datasets and arrays that are nearly sorted, as it requires fewer element comparisons and shifts in such cases.

Insertion Sort Algorithm

Now we know the working principle of the insertion sort algorithm, let's discuss its algorithm in step by step manner:

1. Start with an unsorted array of elements.
 

2. Set a loop variable i to 1, representing the current element being processed.
 

3. While i is less than the length of the array:
 

   a. Set a variable key to the value of the current element at index i.
 

   b. Set a variable j to i - 1, representing the index of the last element in the sorted portion.
 

   c. While j is greater than or equal to 0 and the element at index j is greater than key:
 

      - Shift the element at index j one position to the right.
 

      - Decrement j by 1.
 

   d. Insert the key element at index j + 1, which is the correct position in the sorted portion.
 

   e. Increment i by 1 to move to the next element.
 

4. Repeat steps 3a-3e until i reaches the end of the array.
 

5. The array is now sorted.

Let’s see how the insertion sort algorithm can be implemented in Java:

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--;
        }
        arr[j + 1] = key;
    }
}

In this implementation, we use a for loop to iterate through the array starting from index 1. We set the current element as the key and compare it with the elements in the sorted portion of the array. We shift the elements greater than the key to the right using a while loop until we find the correct position for the key element. Finally, we insert the key element into its correct position.

Simple Java Program to Sort an Array Using Insertion Sort Algorithm

Let's see how we can implement the insertion sort algorithm in a complete Java program to sort an array:

public 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--;
            }
            arr[j + 1] = key;
        }
    }

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

    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 12, 1, 6};
        System.out.println("Original array:");
        printArray(arr);
        insertionSort(arr);
        System.out.println("Sorted array:");
        printArray(arr);
    }
}

You can also try this code with Online Java Compiler

Run Code

In this program:
 

1. We define the `insertionSort` method that takes an integer array as input. It implements the insertion sort algorithm as described in the previous section.
 

2. We define a helper method `printArray` that takes an integer array & prints its elements.
 

3. In the `main` method:

   - We create an unsorted integer array `arr`.

   - We print the original array using the `printArray` method.

   - We call the `insertionSort` method to sort the array.

   - We print the sorted array using the `printArray` method.

Output

Original array:
5 2 8 12 1 6
Sorted array:
1 2 5 6 8 12

The program shows how to use the insertion sort algorithm to sort an array of integers. The `insertionSort` method modifies the original array in place, which results in a sorted array.

You can modify the `arr` array in the `main` method to test the insertion sort algorithm with different input arrays.

Time and Space Complexities

Time Complexity

Worst Case: O(n^2)

  - In the worst case, when the array is reverse-sorted, the insertion sort algorithm requires the maximum number of comparisons and shifts.
 

  - For each element, it needs to compare and shift all the previous elements, resulting in a quadratic time complexity.
 

Average Case: O(n^2)

  - On average, the insertion sort algorithm still requires a quadratic number of comparisons and shifts.
 

  - The number of comparisons and shifts depends on the initial order of the elements in the array.
 

Best Case: O(n)

  - In the best case, when the array is already sorted, the insertion sort algorithm performs only one comparison for each element.
 

  - It requires a linear number of comparisons, resulting in a time complexity of O(n).
 

The time complexity of insertion sort makes it less efficient for large datasets compared to more advanced sorting algorithms like Merge Sort or Quick Sort. However, it performs well for small arrays or arrays that are nearly sorted.

Space Complexity

- The space complexity of insertion sort is O(1), meaning it requires constant extra space.
 

- Insertion sort is an in-place sorting algorithm, as it modifies the original array without requiring any significant additional storage.
 

- It only uses a few variables to keep track of the current element, the key, and the position for comparison and shifting.
 

The constant space complexity is one of the advantages of insertion sort, as it doesn't consume extra memory proportional to the input size.
 

Note: Always remember that the actual running time of the insertion sort algorithm can vary depending on the specific implementation and the programming language used. However, the general time and space complexity analysis is similar to most implementations.

Insertion Sort Applications

1. Small datasets: Insertion sort is often used when the input size is small. For small arrays, insertion sort can be faster than more complex algorithms like Merge Sort or Quick Sort due to its simplicity and low overhead. In such cases, the constant factors associated with insertion sort can make it a practical choice.
 

2. Nearly sorted arrays: Insertion sort performs efficiently when the input array is already nearly sorted. If the array is almost in the correct order with only a few elements out of place, insertion sort can quickly sort the array with a minimal number of comparisons and shifts. It takes advantage of the existing order and requires fewer iterations to sort the array fully.
 

3. Hybrid sorting algorithms: Insertion sort is commonly used as a base case or subroutine in hybrid sorting algorithms. For example, in the Timsort algorithm (used in Java's Arrays.sort() and Python's sorted()), insertion sort is applied to small subarrays before merging them. This hybrid approach combines the strengths of insertion sort for small arrays with the efficiency of Merge Sort for larger arrays.
 

4. Online algorithms: Insertion sort is an online algorithm, which means it can sort elements as they arrive without requiring the entire array to be available upfront. This property makes insertion sort useful in scenarios where data is streaming or arriving in real-time, and sorting needs to be performed incrementally.
 

5. Educational purposes: Insertion sort is often taught in introductory computer science courses and used for educational purposes. Its simplicity and intuitive nature make it a good starting point for understanding sorting algorithms and their implementation. It serves as a foundation for learning more advanced sorting techniques.
 

6. In-place sorting: Insertion sort is an in-place sorting algorithm, meaning it sorts the array without requiring additional storage space. This can be useful when memory is limited, or the cost of allocating extra memory is high. In-place sorting is also very useful when you are dealing with large datasets that cannot fit entirely in memory.

When to Use Insertion Sort

Best Use Cases

1. Small Data Sets

Insertion Sort is highly effective for small arrays where overhead from more complex algorithms like Merge Sort isn't justified. For instance, if you're sorting user-entered form data with just a few fields, the simplicity and speed of Insertion Sort can outperform more advanced methods:

int[] values = {4, 3, 2, 1}; // Small array; low overhead 

Its average time complexity of O(n²) is offset by minimal setup, making it ideal for datasets under 20–30 elements.

2. Nearly Sorted Arrays

When the array is already mostly sorted, Insertion Sort performs nearly in linear time O(n). It only needs to shift a few elements, making it suitable for real-time data like sensor logs or event streams.

3. Online Sorting

Insertion Sort is suitable for "online" sorting—i.e., sorting data as it arrives. Since it doesn’t require access to the full array upfront, it's useful in stream-based Java applications where data is continuously appended.

Limitations of Insertion Sort

1. Inefficient for Large Data Sets

With a time complexity of O(n²) in the worst case, Insertion Sort becomes impractical for large datasets. Java applications requiring sorting of thousands of entries—like e-commerce catalogs or analytics—will benefit more from Merge or Quick Sort.

2. Not Suitable for Randomly Ordered Data

When the data is highly unsorted, the number of comparisons and shifts grows rapidly, making it slow. For example:

int[] data = {89, 1, 67, 22, 11, 90, 45}; // Random order = poor performance 

3. Lacks Parallelization

Unlike Merge Sort, Insertion Sort isn’t easily parallelizable. In Java multi-threaded environments, this limits its scalability, especially in performance-critical applications.

Comparison with Other Sorting Algorithms

Insertion Sort vs Bubble Sort

While both are O(n²) algorithms, Insertion Sort tends to perform fewer swaps than Bubble Sort, making it faster in practice. Bubble Sort blindly compares adjacent elements throughout the list, while Insertion Sort inserts values in their correct position as it progresses. For instance, Insertion Sort handles nearly sorted data in O(n) time, which Bubble Sort cannot match. In terms of educational clarity, both are easy to understand, but Insertion Sort provides more practical performance.

Insertion Sort vs Selection Sort

Selection Sort is not a stable sort and performs a fixed number of comparisons, even if the array is sorted. Insertion Sort, on the other hand, can exit early and is stable. If maintaining the order of duplicate elements matters (like sorting names within the same score), Insertion Sort is the better choice. Selection Sort may be slightly better where data movement (swaps) is more expensive than comparisons.

Insertion Sort vs Merge Sort

Merge Sort is significantly faster for large datasets due to its O(n log n) performance and is better suited for applications like file sorting or backend services in Java. However, Merge Sort uses additional space, unlike Insertion Sort, which works in-place. Insertion Sort is better for small or nearly sorted datasets, or in constrained environments like microcontrollers or embedded Java devices.

Real-World Applications

1. Embedded Systems or Low-Memory Devices

In environments like smartwatches or IoT devices where memory is extremely limited, Insertion Sort’s in-place sorting is beneficial. Java applications running on embedded JVMs can use this algorithm to sort small sensor data arrays or settings configurations quickly and efficiently.

2. Educational Tools and Learning Platforms

Due to its simplicity and visual traceability, Insertion Sort is widely used in Java-based educational platforms and IDEs to demonstrate core sorting concepts. Students can easily understand how data moves and why certain decisions are made during sorting. It also helps in visual debugging for beginner projects.

3. Real-Time Log or Event Stream Sorting

Java applications that collect nearly sorted logs or event timestamps (e.g., from a UI event listener or IoT device feed) can use Insertion Sort to maintain order with minimal processing. It can be integrated into data ingestion modules to organize incoming records in real-time with very low latency.

Frequently Asked Questions

Is insertion sort stable?

Yes, insertion sort is a stable sorting algorithm. It maintains the relative order of equal elements during the sorting process.

Can insertion sort handle duplicate elements?

Yes, insertion sort can handle arrays with duplicate elements. It preserves the relative order of equal elements, ensuring stability.

Is insertion sort an in-place sorting algorithm?

Yes, insertion sort is an in-place sorting algorithm. It sorts the array without requiring additional storage space.

Conclusion

In this article, we discussed the insertion sort algorithm, a simple but efficient sorting technique, in detail. We looked into its working principle, implemented it using Java code, and analyzed its time and space complexities. We also discussed its applications and advantages in specific scenarios. Insertion sort, with its simplicity and efficiency for small and nearly sorted arrays, especially when memory is limited or the input size is small.