Insertion Sort Algorithm

Learn the card-sorting algorithm that builds sorted arrays one element at a time

🃏 What is Insertion Sort?

Insertion Sort works like sorting playing cards in your hand. You pick up cards one by one and insert each into its correct position among the already sorted cards. It's efficient for small datasets and nearly sorted arrays! 


# Insertion Sort in action!
def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

# Example
numbers = [64, 34, 25, 12, 22, 11, 90]
print("Sorted:", insertion_sort(numbers))
O(n²)
Worst Case
O(n)
Best Case
Stable
Algorithm

Insertion Sort Characteristics

🔄

Stable Sorting

Maintains relative order of equal elements

Order Preserved Reliable
⚡

Adaptive

Performs better on nearly sorted data

O(n) Best Case Smart Algorithm
🎯

In-Place

Uses only O(1) extra memory space

Memory Efficient No Extra Arrays
🔄

Online Algorithm

Can sort data as it arrives

Real-time Streaming Data

Lesson 1: Understanding the Insertion Process

Insertion Sort builds the sorted array one element at a time by inserting each element into its correct position:

Insertion Sort Steps: [5, 2, 4, 6, 1, 3]

5
2
4
6
1
3
0
1
2
3
4
5
Step-by-Step Insertion Sort 
def insertion_sort_detailed(arr):
    """Insertion Sort with detailed steps"""
    print(f"Starting array: {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
        
        print(f"\nStep {i}: Inserting {key}")
        print(f"  Sorted portion: {arr[:i]}")
        print(f"  Unsorted portion: {arr[i:]}")
        
        # Move elements greater than key one position ahead
        moves = 0
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
            moves += 1
            print(f"    Moving {arr[j + 2]} to position {j + 2}")
        
        # Insert the key at its correct position
        arr[j + 1] = key
        if moves > 0:
            print(f"    Inserted {key} at position {j + 1}")
        else:
            print(f"    {key} already in correct position")
        
        print(f"  Array after step {i}: {arr}")
    
    return arr

# Example usage
numbers = [5, 2, 4, 6, 1, 3]
sorted_numbers = insertion_sort_detailed(numbers.copy())

Lesson 2: Basic Implementation

Let's implement Insertion Sort step by step:

Simple Insertion Sort 
def insertion_sort(arr):
    """
    Simple Insertion Sort implementation
    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     # Start comparing with previous element
        
        # 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               # Move to the previous element
        
        # Insert key at its correct position
        arr[j + 1] = key
    
    return arr

# Test the function
test_array = [64, 34, 25, 12, 22, 11, 90]
print("Original array:", test_array)
sorted_array = insertion_sort(test_array.copy())
print("Sorted array:", sorted_array)

Lesson 3: Insertion Sort Variations

Here are different ways to implement and optimize Insertion Sort:

Insertion Sort Variations

🔹Binary Insertion Sort (Optimized) 

def binary_insertion_sort(arr):
    """Insertion Sort with binary search for finding position"""
    
    def binary_search(arr, val, start, end):
        """Find the position where val should be inserted"""
        if start == end:
            return start if arr[start] > val else start + 1
        
        if start > end:
            return start
        
        mid = (start + end) // 2
        
        if arr[mid] < val:
            return binary_search(arr, val, mid + 1, end)
        elif arr[mid] > val:
            return binary_search(arr, val, start, mid - 1)
        else:
            return mid
    
    for i in range(1, len(arr)):
        key = arr[i]
        # Find location to insert using binary search
        pos = binary_search(arr, key, 0, i - 1)
        
        # Shift elements to make space
        for j in range(i - 1, pos - 1, -1):
            arr[j + 1] = arr[j]
        
        # Insert the key
        arr[pos] = key
    
    return arr

🔹Recursive Insertion Sort 

def recursive_insertion_sort(arr, n=None):
    """Recursive implementation of Insertion Sort"""
    if n is None:
        n = len(arr)
    
    # Base case
    if n <= 1:
        return arr
    
    # Sort first n-1 elements
    recursive_insertion_sort(arr, n - 1)
    
    # Insert the nth element at its correct position
    last = arr[n - 1]
    j = n - 2
    
    while j >= 0 and arr[j] > last:
        arr[j + 1] = arr[j]
        j -= 1
    
    arr[j + 1] = last
    return arr

🔹Insertion Sort with Sentinel 

def insertion_sort_sentinel(arr):
    """Insertion Sort with sentinel to avoid boundary checks"""
    if not arr:
        return arr
    
    # Find minimum element and place it at the beginning
    min_idx = 0
    for i in range(1, len(arr)):
        if arr[i] < arr[min_idx]:
            min_idx = i
    
    # Swap minimum element to the beginning (acts as sentinel)
    arr[0], arr[min_idx] = arr[min_idx], arr[0]
    
    # Now perform insertion sort without boundary checks
    for i in range(2, len(arr)):
        key = arr[i]
        j = i - 1
        
        # No need to check j >= 0 because sentinel guarantees termination
        while arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        
        arr[j + 1] = key
    
    return arr

🔹Insertion Sort for Linked Lists 

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def insertion_sort_linked_list(head):
    """Insertion Sort for linked lists"""
    if not head or not head.next:
        return head
    
    # Create a dummy node to simplify insertion
    dummy = ListNode(0)
    current = head
    
    while current:
        # Store next node before we break the link
        next_node = current.next
        
        # Find the correct position to insert current node
        prev = dummy
        while prev.next and prev.next.val < current.val:
            prev = prev.next
        
        # Insert current node
        current.next = prev.next
        prev.next = current
        
        # Move to next node
        current = next_node
    
    return dummy.next

# Helper function to create linked list from array
def create_linked_list(arr):
    if not arr:
        return None
    head = ListNode(arr[0])
    current = head
    for val in arr[1:]:
        current.next = ListNode(val)
        current = current.next
    return head

# Helper function to convert linked list to array
def linked_list_to_array(head):
    result = []
    current = head
    while current:
        result.append(current.val)
        current = current.next
    return result

Lesson 4: Performance Analysis

Understanding when Insertion Sort shines:

Performance Analysis 
import time
import random

def analyze_insertion_sort():
    """Analyze Insertion Sort performance on different inputs"""
    
    def create_nearly_sorted(size, disorder_percent=10):
        """Create a nearly sorted array"""
        arr = list(range(size))
        swaps = max(1, size * disorder_percent // 100)
        for _ in range(swaps):
            i, j = random.randint(0, size-1), random.randint(0, size-1)
            arr[i], arr[j] = arr[j], arr[i]
        return arr
    
    sizes = [100, 500, 1000]
    
    for size in sizes:
        print(f"\n=== Array Size: {size} ===")
        
        test_cases = {
            "Random": [random.randint(1, 1000) for _ in range(size)],
            "Sorted": list(range(size)),
            "Reverse Sorted": list(range(size, 0, -1)),
            "Nearly Sorted (10%)": create_nearly_sorted(size, 10),
            "Nearly Sorted (5%)": create_nearly_sorted(size, 5)
        }
        
        for case_name, arr in test_cases.items():
            start_time = time.time()
            insertion_sort(arr.copy())
            end_time = time.time()
            
            print(f"{case_name:20}: {(end_time - start_time)*1000:.2f} ms")

def count_operations():
    """Count comparisons and shifts for different inputs"""
    
    def insertion_sort_with_counts(arr):
        comparisons = 0
        shifts = 0
        
        for i in range(1, len(arr)):
            key = arr[i]
            j = i - 1
            
            while j >= 0:
                comparisons += 1
                if arr[j] > key:
                    arr[j + 1] = arr[j]
                    shifts += 1
                    j -= 1
                else:
                    break
            
            arr[j + 1] = key
        
        return arr, comparisons, shifts
    
    test_arrays = {
        "Sorted [1,2,3,4,5]": [1, 2, 3, 4, 5],
        "Reverse [5,4,3,2,1]": [5, 4, 3, 2, 1],
        "Random [3,1,4,2,5]": [3, 1, 4, 2, 5]
    }
    
    print("\n=== Operation Counts ===")
    for name, arr in test_arrays.items():
        _, comps, shifts = insertion_sort_with_counts(arr.copy())
        print(f"{name:20}: {comps:2d} comparisons, {shifts:2d} shifts")

# Run analysis
analyze_insertion_sort()
count_operations()

Practical Applications

Best Use Cases

  • Small datasets (n < 50)
  • Nearly sorted data
  • Online algorithms
  • Stable sorting required

Real-World Examples

  • Sorting playing cards
  • Maintaining sorted lists
  • Hybrid sorting algorithms
  • Streaming data processing

Advantages

  • Simple implementation
  • Stable and adaptive
  • In-place sorting
  • Good for small inputs

Disadvantages

  • O(n²) worst case
  • More writes than selection sort
  • Not suitable for large datasets
  • Poor performance on reverse sorted

Practice Project: Library Book Organizer

Let's create a program that organizes library books using Insertion Sort:

Library Book Organizer 
class Book:
    def __init__(self, title, author, year, isbn):
        self.title = title
        self.author = author
        self.year = year
        self.isbn = isbn
    
    def __str__(self):
        return f"'{self.title}' by {self.author} ({self.year})"
    
    def __repr__(self):
        return self.__str__()

class LibraryOrganizer:
    def __init__(self):
        self.books = []
    
    def add_book(self, book):
        """Add a book and maintain sorted order using insertion sort"""
        self.books.append(book)
        # Use insertion sort to maintain order
        self._insertion_sort_by_title()
    
    def _insertion_sort_by_title(self):
        """Sort books by title using insertion sort"""
        for i in range(1, len(self.books)):
            key_book = self.books[i]
            j = i - 1
            
            while j >= 0 and self.books[j].title.lower() > key_book.title.lower():
                self.books[j + 1] = self.books[j]
                j -= 1
            
            self.books[j + 1] = key_book
    
    def sort_by_author(self):
        """Sort books by author using insertion sort"""
        for i in range(1, len(self.books)):
            key_book = self.books[i]
            j = i - 1
            
            while j >= 0 and self.books[j].author.lower() > key_book.author.lower():
                self.books[j + 1] = self.books[j]
                j -= 1
            
            self.books[j + 1] = key_book
    
    def sort_by_year(self, ascending=True):
        """Sort books by publication year"""
        for i in range(1, len(self.books)):
            key_book = self.books[i]
            j = i - 1
            
            if ascending:
                condition = self.books[j].year > key_book.year
            else:
                condition = self.books[j].year < key_book.year
            
            while j >= 0 and condition:
                self.books[j + 1] = self.books[j]
                j -= 1
                if j >= 0:
                    if ascending:
                        condition = self.books[j].year > key_book.year
                    else:
                        condition = self.books[j].year < key_book.year
            
            self.books[j + 1] = key_book
    
    def display_books(self, title="Library Books"):
        """Display all books"""
        print(f"\n📚 {title}")
        print("-" * 50)
        for i, book in enumerate(self.books, 1):
            print(f"{i:2d}. {book}")
    
    def search_by_title(self, title):
        """Search for a book by title (works best on sorted list)"""
        title_lower = title.lower()
        for book in self.books:
            if title_lower in book.title.lower():
                return book
        return None

def main():
    # Create library organizer
    library = LibraryOrganizer()
    
    # Add some books (they'll be automatically sorted by title)
    books_to_add = [
        Book("The Great Gatsby", "F. Scott Fitzgerald", 1925, "978-0-7432-7356-5"),
        Book("To Kill a Mockingbird", "Harper Lee", 1960, "978-0-06-112008-4"),
        Book("1984", "George Orwell", 1949, "978-0-452-28423-4"),
        Book("Pride and Prejudice", "Jane Austen", 1813, "978-0-14-143951-8"),
        Book("The Catcher in the Rye", "J.D. Salinger", 1951, "978-0-316-76948-0"),
        Book("Animal Farm", "George Orwell", 1945, "978-0-452-28424-1"),
        Book("Lord of the Flies", "William Golding", 1954, "978-0-571-05686-2")
    ]
    
    print("Adding books to library (auto-sorted by title)...")
    for book in books_to_add:
        library.add_book(book)
        print(f"Added: {book}")
    
    # Display books sorted by title
    library.display_books("Books Sorted by Title")
    
    # Sort by author
    library.sort_by_author()
    library.display_books("Books Sorted by Author")
    
    # Sort by year (oldest first)
    library.sort_by_year(ascending=True)
    library.display_books("Books Sorted by Year (Oldest First)")
    
    # Sort by year (newest first)
    library.sort_by_year(ascending=False)
    library.display_books("Books Sorted by Year (Newest First)")
    
    # Search functionality
    print("\n🔍 Search Results:")
    search_result = library.search_by_title("1984")
    if search_result:
        print(f"Found: {search_result}")
    else:
        print("Book not found")
    
    # Demonstrate online sorting (adding books to already sorted list)
    print("\n📖 Adding new books to sorted library:")
    new_books = [
        Book("Brave New World", "Aldous Huxley", 1932, "978-0-06-085052-4"),
        Book("Fahrenheit 451", "Ray Bradbury", 1953, "978-1-4516-7331-9")
    ]
    
    for book in new_books:
        library.add_book(book)
        print(f"Added and sorted: {book}")
    
    library.display_books("Final Library Collection")

# Run the library organizer
main()

🧠 Test Your Knowledge

What is the best-case time complexity of Insertion Sort?

Insertion Sort is a _____ sorting algorithm.

When does Insertion Sort perform best?