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)
   • Solution

Merge Sort

• demo
• 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;
    }
};