DSA Visual

Insertion Sort

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

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

Implementation

1def insertion_sort(arr: list[int]) -> list[int]:
2    if arr is None or len(arr) == 0:
3        raise ValueError("Array is empty")
4    for i in range(1, len(arr)):
5        key = arr[i]
6        j = i - 1
7        while j >= 0 and arr[j] > key: # while elements are greater than key
8            arr[j + 1] = arr[j] # shift element to the right
9            j -= 1 # move to the previous element
10        arr[j + 1] = key # insert key at the correct position
11    return arr
12

Insertion Sort Animation

Waiting for input...

No steps to display. Please provide input to visualize the algorithm.

-

More in Sorting

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