請實作 合併排序（Merge Sort） 演算法，將一個整數陣列 $\text{arr}$ 排序為 非嚴格遞增序列（允許重複元素，數字由小到大排列）。

你需要實作並上傳兩個函式：

1. merge

函式功能如下：

• 對於陣列 arr，已知區間 $[\text{left}, \text{mid})$ 與 $[\text{mid}, \text{right})$ 分別為非嚴格遞增序列。
• 請將整個區間 $[\text{left}, \text{right})$ 排序為非嚴格遞增序列（即完成合併的動作）。

2. merge_sort

函式功能如下：

• 將陣列 arr 中任意區間 $[\text{left}, \text{right})$ 排序為非嚴格遞增序列。
• 可以遞迴呼叫自己，並搭配 merge 完成排序。

使用範例程式碼

評測時，你所實作的 merge 與 merge_sort 函式會被放入以下程式碼中進行測試：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void merge(vector<int> &arr, int left, int mid, int right){
    // TODO
}

void merge_sort(vector<int> &arr, int left, int right){
    // TODO
}

int main() {
    // input
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    // process
    merge_sort(arr, 0, n);

    // output
    for (auto x : arr) {
        cout << x << " ";
    }
    cout << "\n";

    return 0;
}

上傳說明

請上傳你實作的 merge 與 merge_sort 函式，並包含你需要使用的標頭檔與命名空間，例如：

#include <...>
using namespace ...;

void merge(vector<int> &arr, int left, int mid, int right){
    // TODO
}

void merge_sort(vector<int> &arr, int left, int right){
    // TODO
}