mergesort.cpp

参加ICPC的acm队员所使用的比赛模板

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

const long MAX=99999999;
template<class T>
void merge(T*& A,int p,int q,int r){
     int n1=q-p+1;
     int n2=r-q;
     T L[n1+1],R[n2+1];
     int i,j,k;
     for(i=0;i<n1;++i)
                      L[i]=A[p+i];
     for(j=0;j<n2;++j)
                     R[j]=A[q+j+1];
     L[n1]=R[n2]=MAX;
     i=j=0;
     for(k=p;k<=r;++k){
                       if(L[i]<=R[j])
                                      A[k]=L[i++];
                       else
                                      A[k]=R[j++];
                                      }
}

template<class T>
void merge_sort(T*& A,int p,int r){
     if(p<r){
             int q=(p+r)/2;
             merge_sort(A,p,q);
             merge_sort(A,q+1,r);
             merge(A,p,q,r);
             }
}

int main(){
    printf("input the quantity of the numbers,if quit,press 0\n");
    int n,i;
    while(scanf("%d",&n)==1 && n!=0){
                          int *A=new int[n+1];
                          for(i=0;i<n;++i)
                                          scanf("%d",A+i);
                          merge_sort(A,0,n-1);
                          printf("The sequence sorted by merge_sort:\n");
                          for(i=0;i<n;++i)
                                          printf("%d ",A[i]);
                          printf("\n");
                          sort(A,A+n);
                          printf("The sequence sorted by the lib function::sort:\n");
                          for(i=0;i<n;++i)
                                          printf("%d ",A[i]);
                          printf("\n");
                          }
    return 0;
}