归并排序.txt

ACM资料大集合

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;

#define NMAX 500002

void Merge(long tr2[],long *tr1,long s,long m,long t)
{
	long k,p,q;
	for(k=s,p=m+1,q=s;k<=m&&p<=t;)
	{
		if(tr2[k]<tr2[p]) {tr1[q++]=tr2[k++];}
		else tr1[q++]=tr2[p++];
	}
	while(k<=m) tr1[q++]=tr2[k++];
	while(p<=t) tr1[q++]=tr2[p++];
}

void msort(long sr[],long *tr1,long s,long t)
{
	long m;
	long tr2[NMAX];
	if(s==t) tr1[s]=sr[s];
	else
	{
		m=(s+t)/2;
		msort(sr,tr2,s,m);
		msort(sr,tr2,m+1,t);
		Merge(tr2,tr1,s,m,t);
	}
}


int main()
{
	long num,i;
	long a[NMAX],b[NMAX];
	scanf("%ld",&num);
	for(i=0;i<num;i++)
		scanf("%ld",&a[i]);
	msort(a,b,0,num-1);
	for(i=0;i<num;i++)
		printf("%ld\n",b[i]);
	return 0;
}