- #include <bits/stdc++.h>
- using namespace std;
- void margearray(int a[], int s, int e)
- {
- int tmp[e-s+1], k = 0, mid = (s+e)/2;
- int i = s, j = mid+1;
- int m = mid, n=e;
- while(i<= m && j <= n)
- {
- if(a[i] <= a[j])
- tmp[k++] = a[i++];
- else
- tmp[k++] = a[j++];
- }
- while(i<=m)
- {
- tmp[k++] = a[i++];
- }
- while(j <= n)
- {
- tmp[k++] = a[j++];
- }
- for(int t = 0; t <k; t++)
- a[s+t] = tmp[t];
- }
- void margesort(int a[], int s, int e)
- {
- if(s < e)
- {
- int mid = (s+e)/2;
- margesort(a, s, mid);
- margesort(a, mid+1, e);
- margearray(a, s, e);
- }
- }
- int main()
- {
- int n;
- while (cin>> n)
- {
- int a[100100];
- for(int i = 0; i <n; i++)
- cin>> a[i];
- margesort(a, 0, n-1);
- for(int i = 0; i < n; i++)
- cout << a[i] << " " ;
- cout << endl;
- }
- }
来源: http://www.bubuko.com/infodetail-2693600.html