Insertion Sort Simulation

Insertion Sort builds a sorted left subarray one element at a time by taking the next key and shifting larger elements right to open its proper slot.

Interactive simulation

Key
-
Scan index
-
Shifts
0
Sorted prefix
1 / 10
Speed
1x
Ready: press Insert Next or Resume to start

Legend

  • Sorted prefix
  • Active key being placed
  • Shifting element right
  • Unsorted tail

Event log

    How to use this simulation

    1. Press Insert Next once to step through one shift/placement event, or press Resume to watch the sorted prefix grow automatically.
    2. Notice how elements greater than the active key shift right while the key settles into its sorted position.
    3. Use Step, Slower (down to 0.25x), Faster (up to 4x), and Reset to explore different inputs.

    1. Growing sorted prefix

    A single element at index 0 starts out trivially sorted. Each step picks key = arr[i] and scans backward through the sorted prefix.

    2. Shifting instead of full swaps

    While arr[j] > key, each larger element shifts right by one position, creating an open slot where key is finally placed.

    3. When Insertion Sort shines

    It runs in O(n) on nearly sorted or small arrays with minimal overhead, though its worst-case and average time are O(n²).

    Related topics