Take the names one at a time and move each one left, exchanging it with every larger neighbor, until it is in place. Everything to its left is already sorted; everything to its right is untouched. Step through it one compare at a time.
1 · Step through the sort
The 16 names from the slides and the code of Insertion.sort() (Program 4.2.4). Each click on Step is one compare - and one exchange if the left neighbor is larger.
Input
5
sorted part a[0, i)the name being insertedits left neighbor (compared)untouched
Code (Program 4.2.4)
What happens
i1
j1
compares0
exchanges0
N²/4 for N = 1664
2 · The trace, one row per insertion
Each row is the array after one pass of the outer loop, as on the lecture slide and in the book (p. 544). The boxed name is the one that was inserted; it stopped at index j. The names between it and position i moved one place right; the faded ones are still untouched.
3 · The cost depends on the input
The same 16 names in four orders, sorted completely. Insertion sort is sensitive to its input (book, p. 548): already sorted input costs one compare per name, reversed input the most.
For N = 16: N − 1 = 15 (best case), N²/4 = 64 (average), N(N − 1)/2 = 120 (worst case). Every exchange fixes exactly one pair that is out of order (an inversion); a reversed array has all 120 pairs out of order. Click random above again for a new random order.
Companion to the insertion sort session (lecture CS.11.C; book §4.2, pp. 543–549, Program 4.2.4 on p. 547). Before: the binary search trace.