Insertion Sort Algorithm

Insertion sort is a simple, intuitive sorting algorithm that builds the final sorted array one element at a time. It works similarly to how you would sort playing cards in your hands, taking one card at a time and inserting it into its correct position among the already sorted cards.

Interactive Visualization

Insertion Sort Visualization

Speed: 800ms

Array Visualization

Legend:

Sorted

Unsorted

Key Element

Comparing

Shifting

How Insertion Sort Works:

• Key Selection: Pick the first element from unsorted partition

• Compare & Shift: Compare key with sorted elements, shift larger ones right

• Insert: Place key in correct position within sorted partition

• Repeat: Continue until all elements are processed

• Time Complexity: O(n²) worst case, O(n) best case

• Space Complexity: O(1) in-place sorting

• Stable: Maintains relative order of equal elements

• Adaptive: Efficient for nearly sorted arrays

In-Place Sorting Strategy

Insertion sort exemplifies an in-place sorting approach that maintains a sorted portion at the beginning of the array and progressively expands it by inserting each new element into its correct position within this sorted region.

1. Select

Take the next unsorted element from the array

2. Compare

Compare with elements in the sorted portion moving backwards

3. Insert

Shift larger elements right and insert at correct position

Key Insight

At any point during the sorting process, the left portion of the array is always sorted. We maintain this invariant by carefully inserting each new element into its proper position, shifting existing elements as needed to maintain order.

How Insertion Sort Works

Step-by-Step Process

Start: Begin with the second element (index 1), as the first element is trivially sorted

Store Key: Save the current element (key) that needs to be positioned

Shift Right: Move all elements larger than key one position to the right

Insert: Place the key in its correct position in the sorted portion

Repeat: Continue with the next unsorted element until array is complete

Example: Sorting [5, 2, 4, 6, 1, 3]

Initial: [5, 2, 4, 6, 1, 3] - sorted portion: [5]

Step 1: [2, 5, 4, 6, 1, 3] - insert 2, sorted: [2, 5]

Step 2: [2, 4, 5, 6, 1, 3] - insert 4, sorted: [2, 4, 5]

Step 3: [2, 4, 5, 6, 1, 3] - 6 already in place, sorted: [2, 4, 5, 6]

Step 4: [1, 2, 4, 5, 6, 3] - insert 1 at beginning, sorted: [1, 2, 4, 5, 6]

Step 5: [1, 2, 3, 4, 5, 6] - insert 3, final sorted array

Pseudocode

ALGORITHM InsertionSort(arr[], n)
BEGIN
    // Start from the second element (first element is trivially sorted)
    FOR i = 1 TO n-1 DO
        key = arr[i]              // Current element to be positioned
        j = i - 1                 // Index of last element in sorted portion
        
        // Shift elements greater than key to the right
        WHILE j >= 0 AND arr[j] > key DO
            arr[j + 1] = arr[j]   // Move element one position right
            j = j - 1             // Move to previous element
        END WHILE
        
        // Insert key at its correct position
        arr[j + 1] = key
    END FOR
END

// Enhanced version with early termination optimization
ALGORITHM OptimizedInsertionSort(arr[], n)
BEGIN
    FOR i = 1 TO n-1 DO
        key = arr[i]
        
        // Early termination: if key is already in correct position
        IF key >= arr[i-1] THEN
            CONTINUE              // Skip to next iteration
        END IF
        
        j = i - 1
        WHILE j >= 0 AND arr[j] > key DO
            arr[j + 1] = arr[j]
            j = j - 1
        END WHILE
        
        arr[j + 1] = key
    END FOR
END

Complexity Analysis

Case	Time Complexity	Space Complexity	Explanation
Best Case	O(n)	O(1)	Array already sorted - no shifting needed
Average Case	O(n²)	O(1)	Random order - half the elements need shifting on average
Worst Case	O(n²)	O(1)	Reverse sorted array - maximum shifting required

Why O(n) Best Case?

• Already Sorted: Each element is compared only with its immediate predecessor
• No Shifting: No elements need to be moved, just n-1 comparisons
• Adaptive Nature: Algorithm detects and exploits existing order
• Linear Performance: Single pass through array with minimal work

Why O(n²) Worst Case?

• Reverse Order: Each element must be moved to the front of the array
• Maximum Shifts: Element i requires i comparisons and i shifts
• Total Operations: 1 + 2 + 3 + ... + (n-1) = n(n-1)/2
• Quadratic Growth: Doubling input size quadruples the work

Performance Characteristics

Small Arrays (n ≤ 50):
Very efficient due to low overhead
Often outperforms O(n log n) algorithms
Excellent choice

Nearly Sorted:
Close to O(n) performance
Minimal shifting required
Ideal scenario

Large Random Data:
O(n²) becomes prohibitive
Billions of operations for large n
Avoid for large datasets

Code Examples

Here are implementations of insertion sort in different programming languages. Each version demonstrates the core algorithm with clear commenting to show the key operations: selection, comparison, shifting, and insertion.

 def insertion_sort(arr):
    """
    Sorts a list using the insertion sort algorithm
    Time Complexity: O(n²) worst case, O(n) best case
    Space Complexity: O(1)
    """
    # Start from the second element (index 1)
    for i in range(1, len(arr)):
        key = arr[i]  # Current element to be positioned
        j = i - 1     # Index of the last element in sorted portion
        
        # Move elements that are greater than key one position ahead
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]  # Shift element to the right
            j -= 1
        
        # Place key at its correct position
        arr[j + 1] = key
    
    return arr

def print_array(arr):
    """Helper function to print the array"""
    print(" ".join(map(str, arr)))

# Example usage
if __name__ == "__main__":
    numbers = [5, 2, 4, 6, 1, 3]
    
    print("Original array:", end=" ")
    print_array(numbers)
    
    insertion_sort(numbers)
    
    print("Sorted array:", end=" ")
    print_array(numbers) 
 import java.util.Arrays;

public class InsertionSort {
    
    /**
     * Sorts an array using the insertion sort algorithm
     * @param arr The array to be sorted
     */
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        
        // Start from the second element (index 1)
        for (int i = 1; i < n; i++) {
            int key = arr[i];  // Current element to be positioned
            int j = i - 1;     // Index of the last element in sorted portion
            
            // Move elements that are greater than key one position ahead
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];  // Shift element to the right
                j--;
            }
            
            // Place key at its correct position
            arr[j + 1] = key;
        }
    }
    
    /**
     * Helper method to print an array
     */
    public static void printArray(int[] arr) {
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        int[] numbers = {5, 2, 4, 6, 1, 3};
        
        System.out.print("Original array: ");
        printArray(numbers);
        
        insertionSort(numbers);
        
        System.out.print("Sorted array: ");
        printArray(numbers);
    }
} 
 #include <vector>
#include <iostream>
using namespace std;

/**
 * Sorts a vector using the insertion sort algorithm
 * @param arr Reference to the vector to be sorted
 */
void insertionSort(vector<int>& arr) {
    int n = arr.size();
    
    // Start from the second element (index 1)
    for (int i = 1; i < n; i++) {
        int key = arr[i];  // Current element to be positioned
        int j = i - 1;     // Index of the last element in sorted portion
        
        // Move elements that are greater than key one position ahead
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];  // Shift element to the right
            j--;
        }
        
        // Place key at its correct position
        arr[j + 1] = key;
    }
}

/**
 * Helper function to print a vector
 */
void printArray(const vector<int>& arr) {
    for (int value : arr) {
        cout << value << " ";
    }
    cout << endl;
}

int main() {
    vector<int> numbers = {5, 2, 4, 6, 1, 3};
    
    cout << "Original array: ";
    printArray(numbers);
    
    insertionSort(numbers);
    
    cout << "Sorted array: ";
    printArray(numbers);
    
    return 0;
} 

Practical Applications

Perfect For

• Small Datasets: Excellent performance for arrays with fewer than 50 elements
• Nearly Sorted Arrays: Adaptive nature provides near-linear performance
• Online Algorithms: Can sort data as it arrives (streaming)
• Educational Purposes: Simple to understand and implement
• Hybrid Algorithms: Used as base case in quicksort and mergesort implementations
• Memory-Constrained Systems: O(1) space complexity ideal for limited memory

Consider Alternatives When

• Large Datasets: O(n²) complexity becomes prohibitively slow
• Reverse-Sorted Data: Worst-case performance every time
• Performance-Critical Applications: O(n log n) algorithms are faster
• Frequent Sorting Operations: Overhead of O(n²) adds up quickly
• Unknown Data Distribution: Can't guarantee good performance

Real-World Applications

Common Uses: Sorting small collections in applications, card game implementations, educational programming, base case for hybrid sorting algorithms, embedded systems with memory constraints

Adaptive Advantages: Maintains sorted order in real-time systems, efficient for maintaining sorted lists with frequent insertions, optimal for nearly sorted data like timestamped events or partially ordered datasets