Mastering Algorithms

Insertion Sort

Overview

Insertion Sort is a simple comparison-based sorting algorithm that builds the final sorted array one element at a time. It works similarly to how you might sort playing cards in your hands - you pick up one card and insert it into its correct position among the cards you're already holding.

The algorithm maintains a sorted subarray at the beginning of the array and repeatedly takes the next element from the unsorted portion and inserts it into the correct position in the sorted portion.

How It Works

The algorithm works by:

  1. Starting with the second element (index 1) as the key
  2. Comparing the key with elements in the sorted subarray to its left
  3. Shifting elements greater than the key one position to the right
  4. Inserting the key into its correct position
  5. Repeating for all remaining elements

Algorithm


InsertionSort(arr):
    n = length of arr
    for i = 1 to n - 1:
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j = j - 1
        arr[j + 1] = key

Implementation


def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        
        # Move elements greater than key one position ahead
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        
        arr[j + 1] = key
    
    return arr

Complexity Analysis

  • Time Complexity:
    • Best Case: O(n) - when array is already sorted
    • Average Case: O(n²)
    • Worst Case: O(n²) - when array is sorted in reverse order
  • Space Complexity: O(1) - only uses a constant amount of extra space

Insertion Sort is efficient for small datasets and nearly sorted arrays. It's adaptive and stable, making it useful in practice despite its O(n²) worst-case complexity.

Characteristics

  • Stable: Yes - equal elements maintain their relative order
  • In-place: Yes - only requires O(1) extra space
  • Adaptive: Yes - efficient for nearly sorted arrays
  • Online: Yes - can sort a list as it receives it

When to Use Insertion Sort

Insertion Sort is useful when:

  • Sorting small datasets (typically < 50 elements)
  • The array is nearly sorted
  • You need a stable, in-place sorting algorithm
  • Used as a subroutine in more advanced algorithms (like Tim Sort)
  • Online sorting is required

Example

Sorting [12, 11, 13, 5, 6]: 

Initial: [12, 11, 13, 5, 6]
Pass 1:  [11, 12, 13, 5, 6]  (insert 11 before 12)
Pass 2:  [11, 12, 13, 5, 6]  (13 is already in place)
Pass 3:  [5, 11, 12, 13, 6]  (insert 5 at beginning)
Pass 4:  [5, 6, 11, 12, 13]  (insert 6 after 5)
Sorted:  [5, 6, 11, 12, 13]

Related Algorithms

Explore other sorting algorithms: