DSA Visual

Insertion Sort

Watch insertion sort build a sorted list one element at a time with smooth animations.

Time O(n²) · Space O(1) · Stable

Insertion Sort Animation

–

Waiting for input...

Color: Compare • Shift • Insert • Processing • Sorted

Implementation

Python
def insertion_sort(arr: list[int]) -> list[int]:
    if arr is None or len(arr) == 0:
        raise ValueError("Array is empty")
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key: # while elements are greater than key
            arr[j + 1] = arr[j] # shift element to the right
            j -= 1 # move to the previous element
        arr[j + 1] = key # insert key at the correct position
    return arr
About Insertion Sort

How Insertion Sort Works

Insertion sort builds the final sorted array one item at a time by repeatedly picking the next element and inserting it into its correct position among the already-sorted elements. It is efficient for small or nearly sorted datasets.

Take the next unsorted element, compare it backwards through the sorted portion, shifting larger elements to the right until you find the correct position. Insert the element there and repeat for all remaining elements.

Complexity

Time
O(n²)
Space
O(1)
Stability
stable

When to Use Insertion Sort

  • Small datasets
  • Nearly sorted data where it runs in near-linear time
  • Online sorting where elements arrive one at a time

More in Sorting

Bubble SortO(n²)Selection SortO(n²)Merge SortO(n log n)Quick SortO(n log n)Counting SortO(n + k)