#include <iostream>
#include <vector>

using namespace std;

vector<int> Merge(const vector<int> &v1, const vector<int> &v2)
{
    vector<int> res;
    int s1 = v1.size(), s2 = v2.size(), i, j;
    /*
    cout << endl;
    for (int i = 0; i < s1; ++i)
        cout << v1[i] << " ";
    cout << endl;
    for (int i = 0; i < s2; ++i)
        cout << v2[i] << " ";
    cout << endl;
    */
    for (i = 0, j = 0; i < s1, j < s2;) {
        if (v1[i] <= v2[j]) {
            res.push_back(v1[i]);
            ++i;
        }
        else {
            res.push_back(v2[j]);
            ++j;
        }
    }
    if (i < s1) {
        for (int var = i; var < s1; ++var)
            res.push_back(v1[var]);
    }
    else {
        for (int var = j; var < s2; ++var)
            res.push_back(v2[var]);
    }
    return res;
}

vector<int> mergeSort(const vector<int> &arr, int left, int right)
{
    // 3 9 7 1 5 4 2
    if (left == right) return vector<int>{arr[left]};
    int m = (left + right) / 2;
    vector<int> first = mergeSort(arr, left, m);
    vector<int> second = mergeSort(arr, m + 1, right);
    vector<int> res = Merge(first, second);
    /*
    for (auto &it : res) cout << it << " ";
    cout << endl;
    */
    return res;
}

int main()
{
    vector<int> arr{3, 9, 7, 1, 5, 4, 2};
    vector<int> res = mergeSort(arr, 0, arr.size() - 1);
    for (auto &it : res) cout << it << " ";
    return 0;
}