Concept Overview

Insertion Sort builds a sorted array one element at a time by taking an element from the unsorted portion and inserting it into its correct position in the sorted portion. It mimics the way people sort a hand of playing cards.

How It Works

• Assume the first element is sorted.
• Take the next element from the unsorted portion and compare it with elements in the sorted portion.
• Shift elements in the sorted portion to make space and insert the element in its correct position.
• Repeat until all elements are processed.

Time and Space Complexity

• Time Complexity:
  • Best Case: O(n) (array is already sorted)
  • Average Case: O(n²)
  • Worst Case: O(n²) (array is reverse sorted)
• Space Complexity: O(1) (in-place sorting)

Why Use Insertion Sort?

• Purpose: Insertion Sort is efficient for small datasets or nearly sorted arrays (adaptive algorithm).
• Relevance: It is used in practice as a subroutine in advanced algorithms like Timsort (used in Python and Java) for handling small subarrays.
• Limitations: Its quadratic complexity limits its use for large, unsorted datasets.

Java Implementation

public class InsertionSort {
    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 the sorted portion to the right
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            // Place the key in its correct position
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        insertionSort(arr);
        System.out.println("Sorted array: " + java.util.Arrays.toString(arr));
    }
}

Best Practices and Pitfalls

• Best Practice: Use Insertion Sort for small or nearly sorted arrays. It performs well in scenarios like online sorting, where data arrives incrementally.
• Pitfall: Avoid using Insertion Sort for large, random datasets, as the number of shifts can be significant in the worst case.