⬇️➕ Insertion Sort

Insertion sort builds a sorted portion of the array one element at a time. It takes the next element from the unsorted portion and inserts it into the correct position among the already-sorted elements by shifting larger elements to the right. It is efficient for small or nearly-sorted arrays and is stable.

Java Implementation (well-commented)

// InsertionSort.java
// Simple insertion sort implementation in Java with comments.

public class InsertionSort {
    // Sorts the input array in ascending order using insertion sort.
    public static void insertionSort(int[] arr) {
        int n = arr.length;

        // Start from the second element (index 1). The subarray arr[0..i-1] is considered sorted.
        for (int i = 1; i < n; i++) {
            // currentValue is the element we want to insert into the sorted portion.
            int currentValue = arr[i];
            // j is used to scan the sorted portion to find the insertion point.
            int j = i - 1;

            // Shift elements of the sorted portion that are greater than currentValue
            // to the right by one position to make space for insertion.
            while (j >= 0 && arr[j] > currentValue) {
                arr[j + 1] = arr[j];
                j--;
            }

            // Insert currentValue into its correct position (j+1).
            arr[j + 1] = currentValue;

            // After this iteration, arr[0..i] is sorted.
        }
    }

    // Helper to print arrays (for demonstration)
    public static void printArray(int[] arr) {
        for (int x : arr) {
            System.out.print(x + " ");
        }
        System.out.println();
    }

    // Example usage
    public static void main(String[] args) {
        int[] data = {9, 5, 1, 4, 3};
        System.out.println("Before sort:");
        printArray(data);

        insertionSort(data);

        System.out.println("After sort:");
        printArray(data);
    }
}
      

Pros & Cons

Pros: Simple to implement, stable, works very well for small datasets and nearly-sorted arrays. It sorts in-place and requires only O(1) extra space.

Cons: Has O(n²) time complexity in the average and worst cases, so it is inefficient for large random arrays compared to faster algorithms like mergesort or quicksort.

Best suited for

Insertion sort is best for small arrays, arrays that are already mostly sorted, or when you need a stable, in-place sort with low overhead.

Quick summary

Insertion sort processes the array left-to-right, inserting each new element into the correct position within the sorted left-side by shifting elements. It is intuitive, stable, and efficient for small or nearly-sorted inputs but not suitable for large unsorted datasets.