Step 3 of 7

43% Complete

Insertion Sort

Learn the efficient adaptive sorting algorithm: Insertion Sort

What is Insertion Sort?

Insertion Sort builds the sorted array one item at a time. It iterates through an input array, and for each element, finds the place it belongs in the sorted portion and inserts it there. It's efficient for small datasets and nearly sorted data.

Like sorting playing cards: you pick up one card and insert it into its correct position in the cards already in your hand.

How Insertion Sort Works

Algorithm Steps

Start with the second element (first is already sorted)
Compare it with elements in the sorted portion
Shift larger elements one position to the right
Insert the element in its correct position
Repeat for each remaining element

Insertion Sort - Visual Example

// Initial array: [5, 2, 8, 1, 9]
// Sorted: [5]  |  Unsorted: [2, 8, 1, 9]
 
// Step 1: Insert 2
// Shift 5 right, insert 2: [2, 5, 8, 1, 9]
 
// Step 2: Insert 8
// 8 > 5, no shift needed: [2, 5, 8, 1, 9]
 
// Step 3: Insert 1
// Shift 8, 5, 2 right, insert 1: [1, 2, 5, 8, 9]
 
// Step 4: Insert 9
// 9 > 8, no shift needed: [1, 2, 5, 8, 9]
 
// Final sorted array: [1, 2, 5, 8, 9]

Implementation

Insertion Sort Implementation

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        
        // Start from second element
        for (int i = 1; i < n; i++) {
            int key = arr[i];  // Element to be inserted
            int j = i - 1;
            
            // Shift elements greater than key one position right
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            
            // Insert key at correct position
            arr[j + 1] = key;
        }
    }
    
    public static void main(String[] args) {
        int[] numbers = {64, 34, 25, 12, 22, 11, 90};
        insertionSort(numbers);
        System.out.println(Arrays.toString(numbers));
        // Output: [11, 12, 22, 25, 34, 64, 90]
    }
}

Optimized Insertion Sort with Binary Search

Binary Insertion Sort

public class BinaryInsertionSort {
    public static void binaryInsertionSort(int[] arr) {
        int n = arr.length;
        
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            
            // Find position using binary search
            int pos = binarySearch(arr, key, i);
            
            // Shift elements
            for (int j = i - 1; j >= pos; j--) {
                arr[j + 1] = arr[j];
            }
            
            // Insert key
            arr[pos] = key;
        }
    }
    
    // Find position to insert key in sorted arr[0...n-1]
    private static int binarySearch(int[] arr, int key, int n) {
        int left = 0, right = n;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] > key) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return left;
    }
}

Time & Space Complexity

Time Complexity

Best: O(n)

Average: O(n²)

Worst: O(n²)

Space Complexity

O(1) - In-place sorting

Only needs one temporary variable

Why Adaptive?

Insertion Sort performs best on nearly sorted data. If data is already mostly sorted, very few shifts are needed, resulting in O(n) performance.

Worst case (reverse sorted) requires O(n²) because each element must be shifted past all previous elements.

Characteristics

✓ Stable: Preserves order of equal elements

✓ In-place: Requires O(1) extra space

✓ Adaptive: Fast on nearly sorted data

✓ Online: Can sort while receiving data

When to Use Insertion Sort

Good for:

Small datasets (n < 50)
Nearly sorted data
Online sorting (data arriving in stream)
When stability is required
Hybrid sorting (base case in Timsort/Introsort)

Avoid for:

Large random datasets
Reverse-sorted data
When O(n log n) guaranteed performance needed

Real-World Usage

Timsort (Python's default sort) uses Insertion Sort for small arrays before merging. Insertion Sort is the base case for many hybrid algorithms.

Why? Small arrays don't benefit from complex algorithms, and Insertion Sort's low overhead makes it faster for n < 50.

Key Takeaways

Insertion Sort builds sorted array incrementally
O(n) on nearly sorted data makes it adaptive and practical
Stable sort preserves order of equal elements
O(1) space complexity makes it memory efficient
Excellent for small datasets and online sorting
Used as base case in production sorting algorithms
Binary Insertion Sort reduces comparisons but not shifts