Back to Arrays & Sorting

Insertion Sort

Insertion Sort builds the sorted array one item at a time. It works similarly to sorting a hand of playing cards: you pick one card at a time and insert it into its correct relative position among the cards already sorted.

         How it Works Step-by-Step:
        Assume the first element (index 0) is already sorted.
Pick the next unsorted element (the key).

            Compare key with elements in the sorted sub-array from right to left.
          
Shift all larger elements one position to the right.
Insert key into its correct slot.
Repeat until all elements are sorted.

      

Python Implementation

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        
        # Shift elements of arr[0..i-1] that are greater than key to 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

Best Case Time: $O(n)$ — Occurs when the array is already sorted (only 1 comparison per element, 0 shifts).
Worst Case Time: $O(n^2)$ — Occurs when the array is sorted in reverse order.
Space Complexity: $O(1)$ Auxiliary space (In-place).
Stability: Stable (Equal values maintain their original relative order).