Merge Sort:

 Merge Sort:

What is Merge Sort?
Merge Sort is a way to arrange numbers in order by splitting the list into smaller parts, sorting those smaller parts, and then merging them back together in the correct order.

How does it work?

• Break the list into two halves.
• Keep splitting each half into smaller halves until each piece has only one number.
• Then, start merging the pieces back together. While merging, arrange the numbers in order.
• Repeat this until the whole list is merged and sorted.

Step-by-step process:

• Split the list into smaller and smaller parts.
• Merge the small parts back together, sorting as you go.

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

• Split:
  [8, 3, 5, 7] → [8, 3] and [5, 7]
  [8, 3] → [8] and [3]
  [5, 7] → [5] and [7]
• Merge (sorting while merging):
  [8] and [3] → [3, 8]
  [5] and [7] → [5, 7]
  Now merge [3, 8] and [5, 7]:
  Compare numbers one by one: [3, 5, 7, 8]

The list is sorted!

Key idea:

• Split the list into small parts.
• Merge the parts back together while arranging the numbers in order.