Skip to content

Insertion Sort

Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time. It works by taking elements from the unsorted portion and inserting them into their correct position in the sorted portion.

Algorithm Overview

The algorithm works by maintaining a sorted portion at the beginning of the array and repeatedly taking the next element from the unsorted portion and inserting it into its correct position in the sorted portion.

Key Features

  • Simple Implementation: Easy to understand and implement
  • Stable: Maintains relative order of equal elements
  • In-Place: Sorts the array without using extra space
  • Adaptive: Performs well on nearly sorted data
  • Online: Can sort a list as it receives it

Time and Space Complexity

  • Time Complexity:
  • Best Case: O(n) - when array is already sorted
  • Average Case: O(n²)
  • Worst Case: O(n²) - when array is reverse sorted
  • Space Complexity: O(1) - sorts in place

Algorithm Steps

  1. Start from the second element (first element is considered sorted)
  2. Compare current element with elements in the sorted portion
  3. Shift larger elements to the right to make space
  4. Insert current element in its correct position
  5. Repeat for all remaining elements

Usage Examples

Basic Usage

from algo.algorithms.sorting.insertion_sort import insertion_sort

# Sort integers
numbers = [64, 34, 25, 12, 22, 11, 90]
sorted_numbers = insertion_sort(numbers)
print(sorted_numbers)  # [11, 12, 22, 25, 34, 64, 90]

# Sort strings
words = ['banana', 'apple', 'cherry']
sorted_words = insertion_sort(words)
print(sorted_words)  # ['apple', 'banana', 'cherry']

# Empty array
result = insertion_sort([])
print(result)  # []

Educational/Debugging

from algo.algorithms.sorting.insertion_sort import insertion_sort_verbose

# See step-by-step process
insertion_sort_verbose([64, 34, 25, 12])

Output: 

Starting insertion sort on: [64, 34, 25, 12]
Initial sorted portion: [64] | Unsorted portion: [34, 25, 12]

Step 1: Inserting 34 into sorted portion
  Current array: [64, 34, 25, 12]
  Sorted portion: [64] | Current element: 34 | Remaining: [25, 12]
  Looking for insertion position for 34:
    64 > 34, shifting 64 right
    Array after shift: [64, 64, 25, 12]
    Inserting 34 at position 0
  After insertion: [34, 64, 25, 12]
  New sorted portion: [34, 64]

Step 2: Inserting 25 into sorted portion
  Current array: [34, 64, 25, 12]
  Sorted portion: [34, 64] | Current element: 25 | Remaining: [12]
  Looking for insertion position for 25:
    64 > 25, shifting 64 right
    Array after shift: [34, 64, 64, 12]
    34 > 25, shifting 34 right
    Array after shift: [34, 34, 64, 12]
    Inserting 25 at position 0
  After insertion: [25, 34, 64, 12]
  New sorted portion: [25, 34, 64]

Step 3: Inserting 12 into sorted portion
  Current array: [25, 34, 64, 12]
  Sorted portion: [25, 34, 64] | Current element: 12 | Remaining: []
  Looking for insertion position for 12:
    64 > 12, shifting 64 right
    Array after shift: [25, 34, 64, 64]
    34 > 12, shifting 34 right
    Array after shift: [25, 34, 34, 64]
    25 > 12, shifting 25 right
    Array after shift: [25, 25, 34, 64]
    Inserting 12 at position 0
  After insertion: [12, 25, 34, 64]
  New sorted portion: [12, 25, 34, 64]

Final sorted array: [12, 25, 34, 64]

Edge Cases Handled

# Empty array
result = insertion_sort([])  # Returns []

# Single element
result = insertion_sort([42])  # Returns [42]

# Already sorted (O(n) performance)
result = insertion_sort([1, 2, 3, 4])  # Returns [1, 2, 3, 4]

# Reverse sorted (O(n²) performance)
result = insertion_sort([4, 3, 2, 1])  # Returns [1, 2, 3, 4]

# Duplicates
result = insertion_sort([3, 1, 3, 1])  # Returns [1, 1, 3, 3]

API Reference

Insertion Sort Algorithm Implementation

Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time. It works by taking elements from the unsorted portion and inserting them into their correct position in the sorted portion.

Time Complexity: O(n²) in worst and average case, O(n) in best case

Space Complexity: O(1) - sorts in place

Stability: Stable (maintains relative order of equal elements)

insertion_sort(arr)

Sort an array using the insertion sort algorithm.

The algorithm works by maintaining a sorted portion at the beginning of the array and repeatedly taking the next element from the unsorted portion and inserting it into its correct position in the sorted portion.

Parameters:

Name Type Description Default
arr List[T]

List of comparable elements to sort

 required

Returns:

Type Description
List[T]

The sorted list (sorted in-place, but also returned for convenience)

Examples:

>>> insertion_sort([64, 34, 25, 12, 22, 11, 90])
[11, 12, 22, 25, 34, 64, 90]

>>> insertion_sort(['banana', 'apple', 'cherry'])
['apple', 'banana', 'cherry']

>>> insertion_sort([])
[]

insertion_sort_verbose(arr)

Insertion sort with detailed step-by-step output for educational purposes.

This version prints each step of the sorting process to help understand how the algorithm works.

Parameters:

Name Type Description Default
arr List[T]

List of comparable elements to sort

 required

Returns:

Type Description
List[T]

The sorted list