Untitled
unknown
plain_text
a year ago
1.3 kB
5
Indexable
Never
#include<iostream> #include<vector> using namespace std; void merge(vector<int> &a, vector<int> &b, vector<int> &res) { int i = 0; int j = 0; int k = 0; while (i < a.size() && j < b.size()) { if (a[i] < b[j]) { res[k] = a[i]; i++; k++; } else { res[k] = b[j]; j++; k++; } } if (i == a.size()) { while (j < b.size()) { res[k] = b[j]; j++; k++; } } if (j == b.size()) { while (i < a.size()) { res[k] = a[i]; i++; k++; } } } void merge_sort(vector<int> &v) { int n = v.size(); if (n == 1) return; int n1 = n / 2; int n2 = n - n / 2; vector<int> a(n1); vector<int> b(n2); for (int i = 0; i < n1; i++) { a[i] = v[i]; } for (int i = 0; i < n2; i++) { b[i] = v[i + n1]; } merge_sort(a); merge_sort(b); merge(a, b, v); } int main() { int arr[] = {1, 4, 5, 7, 3, 5}; int n = sizeof(arr) / sizeof(arr[0]); vector<int> v(arr, arr + n); for (int i = 0; i < v.size(); i++) { cout << v[i] << " "; } cout << endl; merge_sort(v); for (int i = 0; i < v.size(); i++) { cout << v[i] << " "; } return 0; }