#include <vector>
#include <queue>
#include <iostream>
#include <tuple>
using namespace std;

void merge(vector<int>& nums, int l, int r){
    int mid = (l + r) / 2;
    int i = l, j = mid + 1;
    vector<int> tmp;
    while(i <= mid && j <= r){
        if(nums[i] <= nums[j]) tmp.push_back(nums[i++]);
        else tmp.push_back(nums[j++]);
    }
    while(i <= mid) tmp.push_back(nums[i++]);
    while(j <= r) tmp.push_back(nums[j++]);

    for(int x = l; x <= r; x++){
        nums[x] = tmp[x - l];
    }
}

void mergeSort(vector<int>& nums, int l, int r){
    //回溯，后序
    if(l >= r) return;
    int mid = (l + r) / 2;
    mergeSort(nums, l, mid);
    mergeSort(nums, mid + 1, r);
    //合并可以写在一起，但是分开清晰
    merge(nums, l, r);
}


int main(){

    return 0;
}