> For the complete documentation index, see [llms.txt](https://wiki.hanzheteng.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://wiki.hanzheteng.com/algorithm/cs/divide-and-conquer.md).

# Divide and Conquer

### Three Steps

* **Divide** the problem into multiple subproblems in smaller size.
* **Conquer** the subproblems recursively; set a straight forward way for base case.
* **Combine** the solutions to the subproblems into the solution for the original problem.

### Master Theorem

* recurrence relation: $$T(n)=a T\left({\frac{n}{b}}\right)+f(n)$$
* $$a>1$$the number of subproblems in the recursion
* $$b>1$$the factor by which the subproblem size is reduced in each recursive call
* and$$f$$is asymptotically positive (positive for sufficiently large$$n$$)
* base case: $$T(c)$$is a constant when$$c$$is a constant
* compare $$n^{\log\_{b}{a}}$$with $$f(n)$$and this will lead to three regimes (>, =, <)
  * in recursion tree, compare root with leaves and see which part dominates
* more reference: CLRS book page 94

![](/files/-MccQZWgzUmY4K5lT2aY)

### Example Code: Merge Sort

```cpp
#include <iostream>
#include <vector>

int merge(std::vector<int>& A, int start, int end, int middle, std::vector<int>& B){
  // combine 
  int i = start;
  int j = middle;
  for (int k = start; k<= end; ++k){
    if (i < middle && (j > end || A[i] <= A[j]))
      B[k] = A[i++];
    else
      B[k] = A[j++];
  }
  for (int k = start; k<= end; ++k){
    A[k] = B[k];
  }
}

int mergeSort(std::vector<int>& A, int start, int end, std::vector<int>& B){
  // divide and conquer
  if (end == start)
    return 0;
  int middle = (start + end + 1) / 2;
  mergeSort(A, start, middle - 1, B);
  mergeSort(A, middle, end, B);
  merge(A, start, end, middle, B);
}

int main(){
  int n;
  std::cin >> n; 
  std::vector<int> score(n);
  std::vector<int> temp(n);
  for (int k = 0; k < n; ++k)
    std::cin >> score[k];

  mergeSort(score, 0, n-1, temp);

  std::cout << n << std::endl;
  for (int k = 0; k < n; ++k)
    std::cout << score[k] << std::endl;

  return 0;
}
```