Sorting Algorithm Visualizer
Speed:
Unsorted
Comparing
Current Element
Sorted
Length:
Insertion Sort
A simple sorting algorithm that builds the final sorted array one item at a time, similar to how you might sort playing cards in your hand.

Statistics

Iterations
0
Swaps
0

Complexity Analysis

Case
Best
Average
Worst
Time
O(n)
O(n²)
O(n²)
Space
O(1)

How It Works

  1. Start with the second element (assume the first element is already sorted)
  2. Compare the current element with the previous elements
  3. If the previous element is greater than the current element, move the previous element one position ahead
  4. Repeat until the correct position for the current element is found, then insert it

Best (O(n))

When the array is already sorted, insertion sort makes only one comparison per element.

Average (O(n²))

For random arrays, insertion sort requires quadratic time.

Worst (O(n²))

When the array is sorted in reverse order, insertion sort must shift each element to the beginning of the array.

function insertionSort(arr) {
  const n = arr.length;

  for (let i = 1; i < n; i++) {
    // Store current element to be inserted
    let key = arr[i];
    let j = i - 1;

    // Move elements greater than key
    // to one position ahead
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }

    // Insert the key at correct position
    arr[j + 1] = key;
  }

  return arr;
}