Now that you know how to insert a value into a sorted subarray, you can implement insertion sort:
  1. Call insert to insert the element that starts at index 1 into the sorted subarray in index 0.
  2. Call insert to insert the element that starts at index 2 into the sorted subarray in indices 0 through 1.
  3. Call insert to insert the element that starts at index 3 into the sorted subarray in indices 0 through 2.
  4. Finally, call insert to insert the element that starts at index n, minus, 1 into the sorted subarray in indices 0 through n, minus, 2.
As a reminder, here's the visualization that steps through the algorithm on a deck of cards:

This content is a collaboration of Dartmouth Computer Science professors Thomas Cormen and Devin Balkcom, plus the Khan Academy computing curriculum team. The content is licensed CC-BY-NC-SA.