归并排序-递归

pwnmelife

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

void merge_vec(vector<int> &sub_vec1, vector<int> &sub_vec2, vector<int> &vec) {
        int i = 0;
        int j = 0;
        while (i < sub_vec1.size() && j < sub_vec2.size()) {
                if (sub_vec1[i] <= sub_vec2[j]) {
                        vec.push_back(sub_vec1[i]);
                        i++;
                }
                else {
                        vec.push_back(sub_vec2[j]);
                        j++;
                }
        }
        for (; i < sub_vec1.size(); i++) {
                vec.push_back(sub_vec1[i]);
        }
        for (; j < sub_vec2.size(); j++) {
                vec.push_back(sub_vec2[j]);
        }
}

void merge_sort(vector<int> &vec) {
        if (vec.size() < 2) {
                return;
        }
        vector<int> sub_vec1;
        vector<int> sub_vec2;
        int mid = vec.size() / 2;
        int i = 0;
        for (i = 0; i < mid; i++) {
                sub_vec1.push_back(vec[i]);
        }
        for (i = mid; i < vec.size(); i++) {
                sub_vec2.push_back(vec[i]);
        }
        merge_sort(sub_vec1);
        merge_sort(sub_vec2);
        vec.clear();
        merge_vec(sub_vec1, sub_vec2, vec);
}



int main() {
        vector<int> test = { 5,-7,9,8,1,4,-3,10,2,0 };
        merge_sort(test);
        for (auto val : test) {
                cout << val << " ";
        }
        cout << endl;
}