Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- void merge(vector<int>& a, int Start, int Mid, int End)
- {
- vector<int> temp(End - Start + 1);
- int i = Start;
- int j = Mid + 1;
- int k = 0;
- while (i <= Mid && j <= End)
- {
- if (a[i] < a[j])//swap (a[i],a[j])//swapping
- {
- temp[k] = a[i];
- i++;
- }
- else
- {
- temp[k] = a[j];
- j++;
- }
- k++;
- }
- while (i <= Mid)
- {
- temp[k] = a[i];
- k++;
- i++;
- }
- while (j <= End)
- {
- temp[k] = a[j];
- k++;
- j++;
- }
- for ( i = Start; i <= End; i++)
- {
- a[i] = temp[i - Start];
- }
- }
- void mergesort(vector<int>& a, int start, int end)
- {
- if (start < end)
- {
- int mid = (start + end) / 2;
- mergesort(a, start, mid);
- mergesort(a, mid + 1, end);
- //assumed that these two functions had been already solved:: Sorted
- //Merge these sorted arrays into final one.
- merge(a, start, mid, end);
- }
- }
- int main()
- {
- int n; cin >> n;
- vector<int> a(n);
- for (int i = 0; i < n; i++)
- {
- cin >> a[i];
- }
- mergesort(a, 0, n - 1);
- for (int i = 0; i < n; i++)
- {
- cout << a[i] << " ";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement