[C++]合併排序法

#include <iostream>
#include <vector>

using namespace std;

vector<long long> merge(vector<long long> left, vector<long long> right){
    vector<long long> result;
    size_t leftIdx = 0, rightIdx = 0;
    while(left.size()>leftIdx && right.size()>rightIdx){
        if(left[leftIdx]<right[rightIdx]){
            result.push_back(left[leftIdx]);
            //left.erase(left.begin());
            ++leftIdx;
        }
        else{
            result.push_back(right[rightIdx]);
            //right.erase(right.begin());
            ++rightIdx;
        }
    }
    while (leftIdx < left.size()) {
        result.push_back(left[leftIdx]);
        ++leftIdx;
    }

    while (rightIdx < right.size()) {
        result.push_back(right[rightIdx]);
        ++rightIdx;
    }
    /*if(left.size()) result.insert(result.end(), left.begin(), left.end());
    else result.insert(result.end(), right.begin(), right.end());*/
    
    return result;
}

vector<long long> mergeSort(vector<long long> arr){
    if (arr.size() <= 1) return arr;
    long long mid = arr.size()/2;
    vector<long long> left(arr.begin(), arr.begin()+mid);
    vector<long long> right(arr.begin()+mid, arr.end());

    return merge(mergeSort(left), mergeSort(right));
}

int main(){
    cin.sync_with_stdio(0);
    cin.tie(0);
    int n,m;
    vector<long long> arr;
    cin>>n;
    arr.reserve(n);
    for(int i=0; i<n; i++){
        cin>>m;
        arr.push_back(m);
    }
    vector<long long> result = mergeSort(arr);
    for(auto &v : result) cout<<v<<" ";
}

mergeSort函式會把一個陣列對半切成兩個陣列，最後那個return會讓他一直切切切，切到只剩一個元素，再組合。註解掉的是原本看網路上教學寫的，現在這個模樣是問chatgpt優化過的😂

我原本以為合併排列法可以解sort!這題，結果還是超時了......