47. Divide and Conquer: Reviewing Merge Sort/Quick Sort

We have already encountered the most fundamental examples of Divide and Conquer (D&C) in sorting.

Characteristics of D&C

• Independence: The subproblems created during the 'Divide' phase must be solved independently of each other. Their solutions do not affect the solutions of other subproblems.
• Identical Structure: The subproblems are usually smaller instances of the main problem.

Example: Merge Sort (Pure D&C)

1. Divide: Split array [1..N] into [1..N/2] and [N/2+1..N].
2. Conquer: Recursively sort the two halves.
3. Combine: Merge the two sorted halves.

Example: Quick Sort (D&C with Partition)

1. Divide: Partition the array around the pivot P.
2. Conquer: Recursively sort the elements to the left of P and the elements to the right of P.
3. Combine: No explicit combination step needed, as the partitioning ensures P is already in place.