Pseudo Code

for i = 1 to n-1:
   key = array[i]
   j = i-1
   while j >= 0 and array[j] > key:
      array[j+1] = array[j]
      j = j-1
   array[j+1] = key

Now, let's connect this pseudocode to our story:

• i is the Card (or Element) in Hand:
  • i represents the current card (or element) we're looking at.
• key is the Chosen Card (or Element):
  • key is the card (or element) we're currently sorting and trying to find the right spot for.
• j is the Sorted Cards (or Elements) in Hand:
  • j represents where we are looking among the already sorted cards (or elements) to find the right spot for our key.
• array is the Entire Deck (or Array):
  • array is our deck of cards (or array of elements) that we're sorting.
• Shifting and Inserting:
  • array[j+1] = array[j] is like physically moving cards to the right to make space for the key.
  • array[j+1] = key is putting our key in the correct spot among the sorted cards.

Insertion Sort is like sorting your cards – taking one at a time, finding its place among the already sorted ones. Simple, isn't it? In the next lesson, we'll see how to turn this understanding into code.