A+DS

Insertion Sort

Sort like you sort a hand of cards.

Think of picking up playing cards one at a time. Each new card gets inserted into the correct position in your already-sorted hand. Insertion Sort works the same way: it grows a sorted portion from left to right, picking up each element and sliding it into place.

  sorted  | unsorted
  [ ✔  ✔ ] | [ key  ?  ?  ]
       ←←←←
    slide to find     pick up key
    correct spot      and insert

  [ ✔  ✔  ✔ ] | [ ?  ?  ]  sorted grows!

How it works

  1. 1Start with the first element as the "sorted hand"
  2. 2Pick up the next element (the "key")
  3. 3Shift larger elements right to make room
  4. 4Insert the key into its correct position

Loading...