Insertion Sort

In this section, you will consider a different approach to sorting that doesn’t require us to iterate across the array multiple times (as selection and bubble sort do), but this benefit, of course, comes with its own additional costs…

• Lecture (Part 0)

  • Watch on Youtube
  • Watch on the CS50 Video Player
  • Download Lecture
  • Lecture Notes

• Lecture (Part 1)

  • Watch on Youtube
  • Watch on the CS50 Video Player
  • Download Lecture
  • Lecture Notes

• Shorts

  • Insertion Sort
  • Insertion Sort (Tommy)

• Notes

  • Insertion Sort

• Supplementary Resources

  • Toptal on Interactive Algorithm Animations

• Thought Questions

  • What advantages does insertion sort have over either selection sort or bubble sort? What disadvantages are there?
  • Under what circumstances, if any, is insertion sort preferable to either of the previous sorts we’ve seen so far?
  • What makes insertion sort fundamentally different from the previous sorts in its approach?

• Problems

  • Sort Race
  • Analyze This