Insertion Sort Algorithm | Simple and Adaptive Sorting Method

Description

Insertion Sort is a simple sorting algorithm that builds the final sorted array one item at a time. It works by iterating through the array and for each element, placing it in its correct position among the previously sorted elements. This algorithm is much like sorting playing cards in your hands, where you pick up one card at a time and insert it into its correct position in the sorted portion of your hand.

How It Works

Start with the first element, which is considered sorted by itself
Take the next element and compare it with the sorted portion
Insert the element into its correct position in the sorted portion
Shift the larger elements one position up to make space
Repeat steps 2-4 until all elements are processed

Visualization

Speed:

Click Start to begin visualization

Implementation


def insertion_sort(arr):
    # Traverse through 1 to len(arr)
    for i in range(1, len(arr)):
        key = arr[i]  # Current element to be inserted
        j = i - 1     # Index of the last element in sorted portion
        
        # Move elements of arr[0..i-1] that are greater than key
        # to one position ahead of their current position
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    
    return arr

# Usage example
if __name__ == "__main__":
    arr = [64, 34, 25, 12, 22, 11, 90]
    print("Original array:", arr)
    insertion_sort(arr)
    print("Sorted array:", arr)


#include <iostream>
#include <vector>

class InsertionSort {
public:
    static void sort(std::vector<int>& arr) {
        int n = arr.size();
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            
            // Move elements of arr[0..i-1] 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--;
            }
            arr[j + 1] = key;
        }
    }
};

// Usage example
int main() {
    std::vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
    
    std::cout << "Original array: ";
    for (int num : arr) std::cout << num << " ";
    std::cout << std::endl;
    
    InsertionSort::sort(arr);
    
    std::cout << "Sorted array: ";
    for (int num : arr) std::cout << num << " ";
    std::cout << std::endl;
    
    return 0;
}


public class InsertionSort
{
    public static void Sort(int[] arr)
    {
        int n = arr.Length;
        for (int i = 1; i < n; i++)
        {
            int key = arr[i];
            int j = i - 1;
            
            // Move elements of arr[0..i-1] 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--;
            }
            arr[j + 1] = key;
        }
    }
    
    // Usage example
    public static void Main(string[] args)
    {
        int[] arr = { 64, 34, 25, 12, 22, 11, 90 };
        
        Console.WriteLine("Original array: " + string.Join(" ", arr));
        Sort(arr);
        Console.WriteLine("Sorted array: " + string.Join(" ", arr));
    }
}

Complexity Analysis

Case	Time Complexity
Best	O(n)
Average	O(n²)
Worst	O(n²)

Advantages and Disadvantages

Advantages

Simple implementation
Efficient for small data sets
Adaptive - runs in O(n) time if array is already sorted
Stable sorting algorithm
In-place algorithm - only requires O(1) additional space

Disadvantages

Quadratic time complexity makes it inefficient for large datasets
Generally performs worse than advanced algorithms like Quick Sort
Requires shifting elements, which can be expensive

Quick Info

Insertion Sort