Computer science Algorithms At your own pace
Understand algorithms.
One step at a time.
Watch the data change, understand each decision and try what you would do.
Insertion
Put each value where it belongs within the part that is already sorted.
The numbers below are positions, starting at 0. Letters distinguish equal values.
The first position already forms a sorted part. The next value must be placed within it, like a card in your hand.
Show pseudocode The active line follows the step
for i = 1 … n − 1:j = iwhile j > 0:if a[j − 1] ≤ a[j]: stopswap(a[j − 1], a[j])j = j − 1// a[0 … i] is sorted
The pseudocode describes the rule. Visual steps also include moments to highlight and explain.
Customize the data You can also repeat values
Compare all three on this listCounters for the complete run
| Algorithm | Comparisons | Swaps |
|---|---|---|
| Insertion | 22 | 18 |
| Selection | 28 | 6 |
| Bubble | 27 | 18 |
Try a sorted or reversed list and see what changes. The selector keeps the same list when switching sorting algorithms.
The idea behind insertion.
Think of sorting cards in your hand. Take the next card and move it left until it fits among the previous ones.
After each pass, the left part is sorted. Its values may still change position when a smaller value arrives.
How does the work grow?
n is the number of values. In a sorted list, each insertion stops after one comparison. In a reverse-sorted list, each value must move through the entire preceding part.
Memory and stability
Algorithm auxiliary memory: O(1). The snapshots saved by this website belong to the visualization, not the algorithm.
A stable algorithm preserves the original order of equal values. Stability: Yes, in this implementation. Try repeated values: the letters let you track their identity.
What would you do next?
A new list with its own data. Predict the next action, then explain what makes it valid. insertion.
The numbers below are positions, starting at 0. Letters distinguish equal values.