vizlearn
Home / Algorithms

Insertion Sort

Algorithms & Data StructuresBy Updated

A simple sorting algorithm that builds the final sorted array one item at a time, much like how you might sort playing cards in your hands.

Parameters

12

Visualization

Step: 0
Click Randomize or Step to begin sorting.

Algorithm Insight

Insertion Sort maintains a sorted sub-list and inserts new elements into their correct position.

  • 1. Assume the first element is already sorted.
  • 2. Pick the next element as the Key.
  • 3. Shift sorted elements that are greater than the Key to the right.
  • 4. Insert the Key into its correct slot.

Complexity

Average Case O(N²)
Space Complexity O(1)

Overview

At each pass, take the first value after the sorted prefix. Shift larger prefix values one position right until the insertion point is open, then place the value there. The prefix remains sorted after every pass.

Keep a sorted prefix

For [5, 2, 4], start with [5] sorted. Insert 2 by shifting 5 right: [2, 5, 4]. Then insert 4 by shifting 5 right: [2, 4, 5]. The animation shows the same shifts. Set Array Size, press Randomize Array, then use Next Step or Auto-Run.

Why input order matters

If the array is already sorted, each value needs only one comparison with the previous value, so the work is linear. If it is reverse sorted, every new value shifts across the entire sorted prefix, so the work grows quadratically. More generally, insertion sort performs work related to the number of inversions—pairs that appear in the opposite order from the sorted result.

The standard algorithm is in-place and stable when it shifts only values strictly greater than the current item. Equal values keep their original order.

When to use it

Insertion sort is useful for small arrays, nearly sorted data, or as the small-partition method inside a faster hybrid sort. It is often easier than a more complex algorithm when the input is tiny. For large, randomly ordered arrays, use a comparison sort with O(n log n) worst-case or expected time, such as merge sort or heapsort.

Common mistakes with Insertion Sort

  • Swapping instead of shifting: repeated swaps do extra writes compared with moving the larger prefix once per step.
  • **Using >= in a stable implementation:** shifting equal values can reverse their relative order.
  • Assuming best-case behavior on arbitrary data: its efficiency depends on how many values are already near their final position.

Sources and next steps

Run it in Python

The sorted region grows from the left and each new item is shifted back into place. The printout marks the boundary with |, and the last section shows why real sort implementations switch to this one for small inputs.

insertion_sort.pyPython 3
Output
How the code works
  1. key = a[i]The item is copied out first, which frees its slot. Everything after this is shifting items into the hole and finally dropping key into wherever the hole ended up.
  2. while j >= 0 and a[j] > key:Two exits: running off the front, or meeting something that is not bigger. The second is the early exit that makes an already sorted input cost O(n) — the condition fails at once, every time.
  3. a[j + 1] = a[j]A shift, not a swap. One write per displaced item rather than three, which is why insertion sort beats bubble sort in practice even though they share a complexity class.
  4. a[j + 1] = keyThe + 1 undoes the last j -= 1 of the loop. Getting this index wrong is the single most common bug in this algorithm.
  5. shiftsThe shift count is the number of inversions in the input. That is why “nearly sorted” is not a vague description here — it is a measurable quantity, and it is exactly what this sort charges you for.
Change one thing
  • Run it on a list of 20 random numbers, then on the same list sorted. The shift count collapses; no O(n²) sort should be able to do that.
  • Replace the shifting loop with repeated swaps. Same output, three times the writes — and now you have written bubble sort inside out.
  • Binary-search for the insertion point instead of scanning. Comparisons drop to O(n log n); the shifts, and therefore the running time, do not move at all.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.




Predict, then reveal
About to run: set Array Size to its maximum (20). Before it does — what happens to the readout?
Committing to an answer first is the point — the reveal runs the experiment on the visualisation above and reads the real value back, so nothing here is scripted.
Check yourself
0 of 3
Answer without scrolling back up.
  1. Insertion sort's running time is driven by:
  2. Why does the inner loop shift items rather than swap them?
  3. Real sort implementations switch to insertion sort for small partitions because:





 Cheat sheet
Insertion Sort
Build a sorted section one element at a time and watch each new value shift left into the position where it belongs.
ALGORITHMS · vizlearn.in/dsa/insertion_sort.html
More in Algorithms
AlgorithmsRecursion and the Call StackAlgorithmsDivide and ConquerAlgorithmsMerge SortAlgorithmsQuick Sort
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact