21. Merge Sort: The Divide and Conquer Approach (Part 1)

Merge Sort is the first O(N log N) algorithm we cover, representing a major leap in efficiency for large data.

Paradigm: Divide and Conquer

Merge Sort is a classic example of the Divide and Conquer paradigm:

1. Divide: Break the problem (the list) into two or more smaller subproblems (sublists) recursively.
2. Conquer: Solve the subproblems recursively. If the sublist is small enough (e.g., size 0 or 1), the problem is trivial.
3. Combine (Merge): Combine the solutions of the subproblems to solve the original problem.

Merge Sort Steps

1. Divide: Continuously split the array into halves until you have N sublists, each containing one element.
2. Merge (The Hard Part): Repeatedly merge the sublists to produce new sorted sublists until there is only one sorted list remaining.