# C++ Divide and Conquer
## Prerequisite: Recursion
Practice Problems:
1. LeetCode 779
2. LeetCode 51

## Divide and Conquer
Practice Problems:
1. [LeetCode 50: Pow(x, n)](https://leetcode.com/problems/powx-n/description/)
- [Solution](https://hackmd.io/@PeterWang/leetcode50)

## Merge Sort
* [demo](https://www.hackerearth.com/practice/algorithms/sorting/merge-sort/visualize/)
* LeetCode 912: Sort an Array

class Solution {
public:
    void mergeSort(vector<int>& nums, int l, int r) {
        if (l >= r) return;
        int mid = (l + r) / 2;
        int i = l, j = mid + 1;
        vector<int> sorted;
        mergeSort(nums, l, mid);
        mergeSort(nums, mid + 1, r);
        while (i <= mid && j <= r) {
            if (nums[i] > nums[j]) {
                sorted.push_back(nums[j++]);
            } else {
                sorted.push_back(nums[i++]);
            }
        }
        while (i <= mid) {
            sorted.push_back(nums[i++]);
        }
        while (j <= r) {
            sorted.push_back(nums[j++]);
        }
        for (int p = l; p <= r; p++) {
            nums[p] = sorted[p - l];
        }
    }
    
    vector<int> sortArray(vector<int>& nums) {
        mergeSort(nums, 0, nums.size() - 1);
        return nums;
    }
};