Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- int a[int(1e5+5)];
- vector<int> left, right;
- void mergesort(int n, int l, int r)
- {
- if (l>=r) return;
- int mid=(l+r)/2;
- mergesort(n, l, mid);
- mergesort(n, mid, r);
- merge(l,r,mid);
- }
- void merge(int l, int r, int mid)
- {
- for (int i=l; i<mid; i++) {
- left.push_back(a[i]);
- }
- for (int i=mid; i<r; i++) {
- right.push_back(a[i]);
- }
- int i=0, j=0, k=l;
- while (i<(mid-l+1) and j<(r-mid+1)) {
- if (left[i]<=right[j])
- a[k++]=left[i++];
- else a[k++]=right[j++];
- while (i<mid-l+1)
- a[k++]=left[i++];
- while (j<r-mid+1)
- a[k++]=right[j++];
- }
- }
- int main()
- {
- int n;
- cin>>n;
- for (int i=0; i<n; i++)
- cin>>a[i];
- mergesort(n, 0, n-1);
- for (int i=0; i<n; i++)
- cout<<a[i]<<" ";
- cout<<endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement