Insertion Sort

Tags

Insertion Sort

Category

Sorting

Difficulty

Easy

Problem Statement

Implement the insertion sort algorithm to sort an array of integers in ascending order. Insertion sort builds the sorted portion of the array one element at a time by repeatedly picking the next unsorted element and inserting it into its correct position within the sorted portion.

Intuition

Think of sorting a hand of playing cards. You pick up one card at a time and slide it into the correct position among the cards already in your hand. Each insertion maintains the sorted order of the left portion of the array.

Approach

  1. Start from the second element (index 1), treating the first element as a sorted subarray.
  2. For each element at index i:
    • Store the current element as the key.
    • Compare it with elements to its left, shifting larger elements one position to the right.
    • Insert the key into the correct position.
  3. Repeat until all elements are processed.

Pseudocode

function insertionSort(array):
    for i from 1 to length(array) - 1:
        j = i
        while j > 0 and array[j] < array[j - 1]:
            swap(array[j], array[j - 1])
            j -= 1
    return array

Time & Space Complexity

  • Time: O(n^2) worst and average case. O(n) best case when the array is already sorted.
  • Space: O(1) — Sorting is done in-place.

Key Insights

  • Insertion sort is a stable sort — equal elements maintain their original relative order.
  • It is adaptive: nearly sorted arrays are handled in nearly O(n) time.
  • For small arrays (roughly n < 20), insertion sort often outperforms more complex algorithms due to low overhead.
  • Many advanced algorithms (like Timsort) use insertion sort as a subroutine for small partitions.

Edge Cases

  • Empty array — nothing to sort.
  • Single-element array — already sorted.
  • Already sorted array — each element is compared once and not moved, giving O(n).
  • Reverse-sorted array — worst case, every element must be shifted to the front.
  • Array with all identical elements — O(n) since no swaps are needed.

Linked mentions