Trace Insertion Sort

Supplied materials

• Paper and pencil; an adult may read aloud. No device, account or purchase is needed.

Learn the idea

Binary search requires sorted input. Sorting is a separate preparation step with its own work. In insertion sort, treat the first item as a sorted prefix; take the next item as key, move larger prefix items one place right, and insert key in the open place. After each pass the prefix grows by one item.

Use fictional codes [6, 2, 5, 3]. On the first pass, key 2 goes before 6. On the second, key 5 goes between 2 and 6. On the third, key 3 goes between 2 and 5. We compare with strict greater-than while shifting, so equal items need not move past each other.

1. Label the initial one-item sorted prefix [6].
2. Insert key 2 and write the full array after the pass.
3. Insert 5, then 3, recording each growing sorted prefix.
4. Check that the final array is increasing and contains the same four codes.

Check your reasoning

Your answer is temporary and is not saved to an account. Download your current answer before leaving or reloading. Written work on paper or in another app stays in your own file.

Take it further

Change the input to [6, 2, 5, 5]. Expected final array: [2, 5, 5, 6]; shift counts by pass are 1, 1, 1, totaling 3. Strict > does not shift an equal 5.

Nothing here is saved to an account or sent to a teacher. The answer download includes your current choice and any checked feedback.