Insertion Sort:

 Insertion Sort:

What is Insertion Sort?
Insertion Sort is a way to arrange a list of numbers in order. We build the sorted list step by step by picking one number at a time and inserting it into its correct position.

How does it work?

• Start with the first number (it’s already sorted because it’s the only one).
• Take the next number and compare it with the ones before it.
• If the number is smaller than the one before, move it back to its correct position.
• Keep repeating this for every number until the whole list is sorted.

Step-by-step process:

• Look at the second number and compare it with the first.
• Insert it in the right place (before or after the first number).
• Take the third number and compare it with the ones before it. Insert it in the right place.
• Repeat this for all the numbers.

Example:
List: [5, 3, 8, 4]

• Start with the first number (5). It’s already sorted.
• Take the second number (3). Compare it with 5. Insert 3 before 5.
  → [3, 5, 8, 4]
• Take the third number (8). Compare it with the sorted numbers (3 and 5). It’s already in the right place.
  → [3, 5, 8, 4]
• Take the fourth number (4). Compare it with 8, then 5. Insert it between 3 and 5.
  → [3, 4, 5, 8]

Now the list is sorted!

Key idea:
Pick one number at a time, compare it with the sorted part of the list, and insert it in the right place.