How to do Insertion Sort in Java

Insertion Sort is a fundamental algorithm in computer science. It is known for its simplicity and ease of implementation, making it an excellent starting point for beginners learning about sorting algorithms.

In this blog post, we’ll cover:

1. How Insertion Sort works, including its pseudocode
2. A step-by-step Java implementation
3. Performance analysis of the algorithm
4. Pros and cons and when to use the algorithm

Insertion Sort’s straightforward approach makes it valuable for:

• Learning basic sorting concepts
• Handling small datasets efficiently
• Understanding more complex sorting algorithms

Let’s dive in and explore this essential sorting technique!

What is Insertion Sort?

Insertion Sort works similarly to how you sort a hand of playing cards. You pick one card at a time and place it in the correct position relative to the cards already sorted. The array is conceptually split into two parts: the sorted and unsorted sections. The algorithm picks one element from the unsorted part and inserts it into its correct position in the sorted part.

Below is our visualization tool for seeing Insertion Sort in real time!

Pseudocode for Insertion Sort

Here’s the step-by-step pseudocode for Insertion Sort:

procedure insertionSort(arr)
    for i = 1 to length(arr) - 1 do
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key do
            arr[j + 1] = arr[j]
            j = j - 1
        arr[j + 1] = key

Step-by-Step Explanation:

• You iterate through the array starting from the second element (index 1).
• Each element is compared with the elements before it and is inserted into its correct position in the sorted portion of the array.
• The process continues until all elements are sorted.

Time Complexity of Insertion Sort

• Best Case: O(n) – This occurs when the input array is already sorted. In this case, Insertion Sort only needs to make a single pass through the array.
• Average Case: O(n²) – On average, the algorithm needs to compare and shift elements, leading to quadratic time complexity.
• Worst Case: O(n²) – The worst-case scenario occurs when the array is sorted in reverse order, requiring maximum comparisons and shifts.

Space Complexity of Insertion Sort

• Space Complexity: O(1) – Insertion Sort is an in-place sorting algorithm, meaning it sorts the array without requiring any additional memory allocation.

Java Implementation of Insertion Sort

public class InsertionSort {

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

        // Start sorting from the second element (index 1)
        for (int i = 1; i < n; i++) {
            int key = arr[i];  // Current element to be sorted
            int j = i - 1;

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

            // Place the key in the correct position
            arr[j + 1] = key;
        }
    }

    // Main method to test the sorting algorithm
    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6};

        // Print the original array
        System.out.println("Original Array: ");
        printArray(arr);

        // Perform insertion sort
        insertionSort(arr);

        // Print the sorted array
        System.out.println("Sorted Array: ");
        printArray(arr);
    }

    // Helper method to print the array
    public static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(STR."\{i} ");
        }
        System.out.println();
    }
}

Explanation:

• The outer loop picks one element (key) starting from the second element of the array.
• The inner while loop shifts elements that are greater than key one position to the right.
• Once the correct position is found, the key is inserted into its place, ensuring that the left part of the array is always sorted.

We will explain how Insertion Sort processes this array element by element and places each element into its correct position in the sorted portion of the array.

Step-by-Step Walkthrough

---

Step 1: First Element (12)

• The first element is already sorted, so nothing needs to be done.
• Array after step 1: [12, 11, 13, 5, 6]

---

Step 2: Second Element (11)

• We compare 11 with 12. Since 11 < 12, we shift 12 one position to the right and insert 11 at the beginning.
• Array after step 2: [11, 12, 13, 5, 6]

---

Step 3: Third Element (13)

• We compare 13 with 12. Since 13 > 12, it is already in the correct position.
• Array after step 3: [11, 12, 13, 5, 6]

---

Step 4: Fourth Element (5)

• We compare 5 with 13, 12, and 11. Since 5 < 11, we shift 13, 12, and 11 one position to the right and insert 5 at the beginning.
• Array after step 4: [5, 11, 12, 13, 6]

---

Step 5: Fifth Element (6)

• We compare 6 with 13, 12, and 11. Since 6 < 11, we shift 13, 12, and 11 one position to the right and insert 6 in its correct position between 5 and 11.
• Array after step 5: [5, 6, 11, 12, 13]

---

Final Sorted Array

After all the steps are complete, the final sorted array is:

[5, 6, 11, 12, 13]

Summary of Steps:

1. The first element is considered sorted.
2. The second element (11) is compared with the first (12) and inserted before it.
3. The third element (13) is larger than the sorted portion and remains in place.
4. The fourth element (5) is smaller than all previous elements and is inserted at the beginning.
5. The fifth element (6) is inserted between 5 and 11, completing the sorting process.

This process is repeated until the entire array is sorted. Insertion Sort works well for small datasets or nearly sorted arrays, as seen here.

Performance Test: Insertion Sort vs Bubble Sort vs Quick Sort

In this section, we’ll evaluate the performance of three well-known sorting algorithms: Insertion Sort, Bubble Sort, and Quick Sort. By testing these algorithms on different arrays — random, sorted, reverse-sorted, and partially sorted — we can better understand their efficiency and behaviour under different conditions.

Why These Algorithms?

• Insertion Sort is a simple algorithm that works efficiently on small or nearly sorted datasets. However, it struggles with large, unsorted data due to its O(n²) time complexity in the average and worst cases.
• Bubble Sort is one of the most straightforward sorting algorithms, but it is generally inefficient for large datasets due to its repeated pairwise comparisons, which result in O(n²) time complexity in the worst case.
• Quick Sort is widely used because of its average-case O(n log n) performance. It performs well on most datasets but can slow down with specific patterns, such as already sorted or reverse-sorted data, depending on how the pivot is chosen.

Types of Arrays Tested:

• Random Arrays: These arrays contain elements in a random order, representing typical real-world datasets.
• Sorted Arrays: These arrays are already in ascending order, representing the best-case scenario for Insertion Sort.
• Reverse-Sorted Arrays: These arrays are in descending order, representing the worst-case scenario for Insertion Sort and Bubble Sort.
• Partially Sorted Arrays: These arrays are half-sorted and half-random, representing real-world cases where data may not be completely unsorted but still requires sorting.

By running this performance test, we aim to identify the strengths and weaknesses of each algorithm and determine which one performs best under various conditions and for different array sizes.

Let’s dive into the performance results and see how each algorithm stacks up!

import java.util.Arrays;
import java.util.Random;

public class SortingPerformanceTest {

    // Insertion Sort implementation
    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;
        }
    }

    // Bubble Sort implementation
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    // Quick Sort implementation
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivot = partition(arr, low, high);
            quickSort(arr, low, pivot - 1);
            quickSort(arr, pivot + 1, high);
        }
    }

    // Partition function for Quick Sort
    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, high);
        return i + 1;
    }

    // Helper function to swap elements
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // Generate a partially sorted array
    public static int[] generatePartiallySortedArray(int size) {
        Random random = new Random();
        int[] arr = random.ints(size, 0, size).toArray();
        Arrays.sort(arr, 0, size / 2);  // Sort the first half, leave the second half unsorted
        return arr;
    }

    // Helper method to run a performance test
    public static void benchmark(String name, Runnable sort) {
        long start = System.nanoTime();
        sort.run();
        long duration = System.nanoTime() - start;
        System.out.printf("%s: %.3f ms%n", name, duration / 1e6);  // Convert nanoseconds to milliseconds
    }

    public static void main(String[] args) {
        int[] sizes = {1000, 5000, 10000};  // Test with array sizes 1000, 5000, and 10000
        Random rand = new Random();

        for (int size : sizes) {
            System.out.println("Array size: " + size);

            // Generate a random array
            int[] randomArray = rand.ints(size, 0, size).toArray();

            // Performance test for random arrays
            benchmark("Insertion Sort (random)", () -> {
                int[] arr = Arrays.copyOf(randomArray, randomArray.length);
                insertionSort(arr);
            });
            benchmark("Bubble Sort (random)", () -> {
                int[] arr = Arrays.copyOf(randomArray, randomArray.length);
                bubbleSort(arr);
            });
            benchmark("Quick Sort (random)", () -> {
                int[] arr = Arrays.copyOf(randomArray, randomArray.length);
                quickSort(arr, 0, arr.length - 1);
            });

            // Generate a sorted array
            int[] sortedArray = Arrays.copyOf(randomArray, randomArray.length);
            Arrays.sort(sortedArray);

            // Performance test for sorted arrays
            benchmark("Insertion Sort (sorted)", () -> insertionSort(Arrays.copyOf(sortedArray, sortedArray.length)));
            benchmark("Bubble Sort (sorted)", () -> bubbleSort(Arrays.copyOf(sortedArray, sortedArray.length)));
            benchmark("Quick Sort (sorted)", () -> quickSort(Arrays.copyOf(sortedArray, sortedArray.length), 0, sortedArray.length - 1));

            // Generate a reverse-sorted array
            int[] reverseArray = Arrays.copyOf(sortedArray, sortedArray.length);
            for (int i = 0; i < reverseArray.length / 2; i++) {
                swap(reverseArray, i, reverseArray.length - i - 1);
            }

            // Performance test for reverse-sorted arrays
            benchmark("Insertion Sort (reverse)", () -> insertionSort(Arrays.copyOf(reverseArray, reverseArray.length)));
            benchmark("Bubble Sort (reverse)", () -> bubbleSort(Arrays.copyOf(reverseArray, reverseArray.length)));
            benchmark("Quick Sort (reverse)", () -> quickSort(Arrays.copyOf(reverseArray, reverseArray.length), 0, reverseArray.length - 1));

            // Generate a partially sorted array
            int[] partiallySortedArray = generatePartiallySortedArray(size);

            // Performance test for partially sorted arrays
            benchmark("Insertion Sort (partially sorted)", () -> insertionSort(Arrays.copyOf(partiallySortedArray, partiallySortedArray.length)));
            benchmark("Bubble Sort (partially sorted)", () -> bubbleSort(Arrays.copyOf(partiallySortedArray, partiallySortedArray.length)));
            benchmark("Quick Sort (partially sorted)", () -> quickSort(Arrays.copyOf(partiallySortedArray, partiallySortedArray.length), 0, partiallySortedArray.length - 1));

            System.out.println();
        }
    }
}

Results

Performance Comparison of Insertion Sort, Bubble Sort, and Quick Sort

Array Size & Configuration	Insertion Sort (ms)	Bubble Sort (ms)	Quick Sort (ms)
1000 (Random)	2.682	4.449	0.410
1000 (Sorted)	0.013	1.822	1.984
1000 (Reverse)	6.422	0.962	2.618
1000 (Partially Sorted)	0.447	0.792	0.194
5000 (Random)	9.148	22.923	0.370
5000 (Sorted)	0.033	5.197	11.387
5000 (Reverse)	4.339	16.898	10.253
5000 (Partially Sorted)	1.682	19.801	0.376
10000 (Random)	9.273	119.407	0.702
10000 (Sorted)	0.066	24.298	46.132
10000 (Reverse)	19.205	66.920	32.402
10000 (Partially Sorted)	6.679	101.361	0.628

Note: Times are rounded to three decimal places for readability. Actual performance may vary due to system conditions.

Key Takeaways:

• Quick Sort is consistently the fastest algorithm:
  • Quick Sort outperformed both Insertion Sort and Bubble Sort across all tests, particularly with random and partially sorted arrays. For example, with 10000 random elements, Quick Sort took just 0.702 ms compared to 119.407 ms for Bubble Sort and 9.273 ms for Insertion Sort.
• Insertion Sort excels on sorted arrays:
  • Insertion Sort performed exceptionally well on sorted arrays, taking just 0.013 ms for 1000 sorted elements and 0.033 ms for 5000 sorted elements. This is because Insertion Sort has a best-case time complexity of O(n) when the array is already sorted.
• Bubble Sort performs poorly on large arrays:
  • Bubble Sort struggles significantly with larger arrays, especially on random and partially sorted arrays. For example, on 10000 random elements, Bubble Sort took 119.407 ms, while Quick Sort took only 0.702 ms.
  • Even for sorted arrays, Bubble Sort remains inefficient compared to Quick Sort and Insertion Sort.
• Insertion Sort and Bubble Sort are both inefficient on reverse-sorted arrays:
  • In the worst case, Insertion Sort and Bubble Sort performed poorly on reverse-sorted arrays due to their O(n²) time complexity. For 10000 reverse-sorted elements, Insertion Sort took 19.205 ms, and Bubble Sort took 66.920 ms, compared to 32.402 ms for Quick Sort.
• Quick Sort remains fast even for larger, partially sorted arrays:
  • Quick Sort’s performance on partially sorted arrays was excellent, handling 10000 partially sorted elements in just 0.628 ms, significantly outperforming both Insertion Sort (6.679 ms) and Bubble Sort (101.361 ms).

Conclusion:

• Quick Sort is the best sorting algorithm for general use, particularly for larger datasets.
• Insertion Sort is highly efficient when dealing with already or nearly sorted data.
• Bubble Sort, while simple, is highly inefficient for large datasets and should be avoided unless dealing with very small arrays.

Why Reverse-Sorted Arrays Are the Worst Case for Insertion Sort and Bubble Sort

Both Insertion Sort and Bubble Sort have worst-case time complexities of O(n²), which is most apparent when they process reverse-sorted arrays. Here’s why reverse-sorted data creates the worst performance for these algorithms:

Insertion Sort:

For Insertion Sort, the algorithm assumes that elements before the current one are already sorted, and it shifts elements to insert the current element in its correct position. In the case of a reverse-sorted array, every element is smaller than the ones that come before it. Therefore, every element has to be compared and shifted to the front of the sorted section.

• For the first element, there are no shifts.
• For the second element, it is compared and shifted once.
• For the third element, it is compared and shifted twice.
• This process continues, resulting in approximately n(n−1)/2n(n-1)/2n(n−1)/2 comparisons and shifts in total, leading to O(n²) time complexity.

Example: For a reverse-sorted array like [5, 4, 3, 2, 1], Insertion Sort will shift 5 four times to the end, then 4 three times, and so on.

Bubble Sort:

In Bubble Sort, the algorithm repeatedly compares adjacent elements and swaps them if they are in the wrong order. With a reverse-sorted array, every comparison results in a swap, pushing the largest element to the end of the array. This process has to be repeated for each element.

• In the first pass, the largest element is moved to the last position.
• In the second pass, the second largest element is moved to the second last position.
• This continues until the entire array is sorted.

Because Bubble Sort requires n-1 comparisons and swaps for each pass and the process is repeated n times, it leads to O(n²) time complexity for reverse-sorted arrays.

Example: For the reverse-sorted array [5, 4, 3, 2, 1], Bubble Sort will compare and swap 5 with 4, then 5 with 3, and so on, moving the largest number to the correct position at each pass.

Summary:

• Reverse-sorted arrays are the worst case for both Insertion Sort and Bubble Sort because both algorithms must move every element to its correct position through many comparisons, shifts (for Insertion Sort), or swaps (for Bubble Sort).
• This behaviour leads to O(n²) performance, making both algorithms highly inefficient for reverse-sorted data, particularly as the array grows.

Pros and Cons of Using Insertion Sort

Pros:

1. Simplicity: Insertion Sort is easy to understand and implement.
2. Efficient for Small Arrays: It performs well on small datasets or nearly sorted arrays.
3. Stable Sorting: It preserves the relative order of equal elements, making it a stable sorting algorithm.
4. In-Place Sorting: Insertion Sort uses constant additional memory (O(1)).

Cons:

1. Inefficient for Large Arrays: Its O(n²) time complexity makes it inefficient for large datasets compared to algorithms like QuickSort or MergeSort.
2. More Comparisons and Shifts: Insertion Sort performs a high number of comparisons and shifts in the worst case.

When to Use Insertion Sort

Insertion Sort is typically used in the following scenarios:

1. Small Arrays: When working with small arrays (e.g., fewer than 20 elements), the simplicity of Insertion Sort makes it a reasonable choice.
2. Nearly Sorted Arrays: Insertion Sort performs exceptionally well on nearly sorted arrays, where it can achieve close to O(n) time complexity.
3. Part of a Hybrid Sorting Algorithm: Insertion Sort is often used as a subroutine in more efficient sorting algorithms like TimSort and IntroSort, where it is employed to handle small partitions.

Conclusion

Insertion Sort is a simple and intuitive algorithm, making it an excellent choice for small or nearly sorted datasets. While it’s not suitable for large datasets due to its O(n²) time complexity, it is still an important algorithm to learn. Its role in hybrid algorithms like TimSort highlights its practical utility for optimizing the performance of complex sorting operations.

Congratulations on reading to the end of this tutorial!

Read the following articles to learn how to implement Insertion Sort:

In Python – How to do Insertion Sort in Python

In C++ – How to Do Insertion Sort in C++

In Rust – How to do Insertion Sort in Rust

Have fun and happy researching!