4.2.1.2 Merge Sort, Quick Sort (Divide and Conquer)

These two algorithms use a powerful idea called "Divide and Conquer."

Divide and Conquer: This strategy means you break a big problem into smaller, easier-to-solve pieces. You solve the small pieces, and then you combine the solutions to solve the original big problem.
Merge Sort:
1. Divide: You keep splitting your list of items in half until you have many tiny lists, each with only one item (a list with one item is always sorted!).
2. Conquer (and Merge): Then, you start merging these tiny sorted lists back together, two by two, making sure the new, larger list is also sorted. You keep merging until you have one big, perfectly sorted list. It's like taking two sorted piles of papers and combining them into one bigger sorted pile.
Quick Sort:
1. Divide: Quick Sort picks one item from the list, called a "pivot." Then, it rearranges the list so that all items smaller than the pivot are on one side, and all items larger than the pivot are on the other side. The pivot is now in its correct sorted position.
2. Conquer: Now, you have two smaller, unsorted lists (one on each side of the pivot). Quick Sort then applies the same process (picking a new pivot, rearranging) to these smaller lists.
3. Combine: You don't need a separate "combine" step, because once all the smaller lists are sorted around their pivots, the whole big list is sorted!