Insertion Sort

Idea

• The algorithm works similar to sorting playing cards in your hands
• Start from the second element, compare with previous elements and insert it in its correct position
• The array is virtually split into a sorted and unsorted part
• Values from the unsorted part are picked and placed in the correct position in the sorted part

Visualization

Implementation

void insertionSort(int arr[]) {  
    int n = arr.length;
    for (int i = 1; i < n; i++) {  
        int key = arr[i];  
        int j = i - 1;  
        
        // Move elements that are greater than key 
        // to one position ahead of their current position
        while (j >= 0 && arr[j] > key) {  
            arr[j + 1] = arr[j];  
            j = j - 1;  
        }  
        arr[j + 1] = key;  
    }  
}  

Time and Space Analysis

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

Properties

• Stable sorting algorithm
• In-place algorithm
• Adaptive: number of operations reduces if array is already somewhat sorted
• Very efficient for small data sets
• More efficient in practice than bubble sort and selection sort

Use Cases

• Small data sets
• Nearly sorted arrays
• When stable sort is required
• When memory space is limited
• Online algorithm (can sort as data is being received)

Variants

• Binary Insertion Sort (uses binary search to find insertion position)
• Shell Sort (extension of insertion sort that allows exchange of items that are far apart)