Insertion Sort in Java

Insertion Sort in Java Programming

In this article, we’ll explore Insertion Sort in Java, covering its algorithm, working process, Java implementation, and time-space complexity along with examples for better understanding.

Insertion Sort is a basic and easy to understand sorting algorithm. It works similarly to how we sort playing cards in our hand by picking one card at a time and placing it in the right position. Although it’s not very efficient for large amounts of data, it works well for small datasets or lists that are already nearly sorted.

What is Insertion Sort?

Insertion Sort is a comparison based sorting algorithm that builds the final sorted array one element at a time. It works by taking one element from the input array and inserting it into its correct position in the sorted part of the array.

Insertion sort in Java

Step by Step Algorithm for Insertion Sort

Let’s go through the step by step explanation of how the Insertion Sort algorithm works:

  1. Start from the second element (index 1), as the single element at index 0 is considered sorted.
  2. Compare the current element with the elements before it.
  3. Shift all elements greater than the current element to one position ahead.
  4. Insert the current element into its correct position.
  5. Repeat steps 2–4 for all elements.

Algorithm Pseudocode

for i = 1 to n-1:
    key = array[i]
    j = i - 1
    while j >= 0 and array[j] > key:
        array[j + 1] = array[j]
        j = j - 1
    array[j + 1] = key

Java Program for Insertion Sort

Run

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; // Shift elements of arr[0..i-1], that are greater than key 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 num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = { 12, 11, 13, 5, 6 };
        System.out.println("Original Array:");
        printArray(arr);

        insertionSort(arr);

        System.out.println("Sorted Array:");
        printArray(arr);
    }
}

Input:

Original Array:
12 11 13 5 6

Output:

Sorted Array:
5 6 11 12 13

Time and Space Complexity Analysis for Insertion Sort

CaseComparisonsTime Complexity
Best CaseAlready SortedO(n)
Average CaseRandom OrderO(n²)
Worst CaseReverse OrderO(n²)

Stable Sorting Algorithm

Insertion sort is a stable sorting algorithm because it preserves the relative order of elements with equal keys.

Example:

Before Sorting: [3a, 2, 3b, 1]

After Sorting: [1, 2, 3a, 3b] (Order of 3a and 3b is preserved)

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Insertion Sort in Java Programming explained
Insertion Sort in Java Programming explained

Recursive Implementation of Insertion Sort in Java

Though insertion sort is usually implemented iteratively, it can also be implemented recursively.

Run
public class RecursiveInsertionSort {

    public static void insertionSortRecursive(int[] arr, int n) {
        if (n <= 1) return; insertionSortRecursive(arr, n - 1); int last = arr[n - 1]; int j = n - 2; while (j >= 0 && arr[j] > last) {
            arr[j + 1] = arr[j];
            j--;
        }

        arr[j + 1] = last;
    }

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

        insertionSortRecursive(arr, arr.length);

        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

Output:

1 3 5 7 9

Advantages and Disadvantages of Insertion Sort:

Advantages:

  • Simple to implement and understand.
  • Efficient for small or nearly sorted datasets.
  • In place and stable.

Disadvantages:

  • Not efficient on large datasets.
  • Time complexity grows quadratically with input size.

To wrap it up….

Insertion Sort is a foundational sorting algorithm in computer science, valued for its simplicity and usefulness with small or nearly sorted data.

While it doesn’t scale well to large datasets due to its O(n²) time complexity, its in place and stable nature makes it a useful tool in specific scenarios and a common interview topic.

By understanding its algorithm, step by step implementation in Java, and space/time complexity, you gain a stronger grasp of how basic sorting mechanisms work, which is essential for advancing to more complex algorithms.

Insertion Sort in Java meme

FAQ's related to Insertion Sort in Java Language

Answer:

When dealing with small datasets or nearly sorted data. It is also used as a subroutine in hybrid sorting algorithms.

Answer:

Yes, in practice. Although both have O(n²) complexity, insertion sort is more efficient than bubble sort in most real world scenarios.

Answer:

It doesn’t change the order of equal elements. When inserting an element, it only shifts greater elements to the right.

Answer:

Yes, insertion sort works for all integers including negative numbers.

Answer:

O(1), as it is an in-place sorting algorithm and doesn’t require additional memory.

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription