Insertion Sort

Insertion Sort builds the sorted array one element at a time by inserting each element into its correct position. It's efficient for small datasets and nearly sorted arrays.

Insertion Sort Visualization

Complexity

Time Complexity: O(n²)

Space Complexity: O(1)

Pseudocode

function InsertionSort(array):
  for i from 1 to length(array)-1:
    key = array[i]
    j = i - 1
    
    while j >= 0 and array[j] > key:
      array[j+1] = array[j]
      j--
    
    array[j+1] = key

Related Algorithms

Bubble Sort

Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. It's easy to understand but inefficient for large datasets.

Time: O(n²) | Space: O(1)

Selection Sort

Selection sort repeatedly selects the smallest element from the unsorted portion and places it at the beginning.

Time: O(n^2) | Space: O(1)