Cod sursa(job #952387)

Utilizator horatiu11Ilie Ovidiu Horatiu horatiu11 Data 23 mai 2013 12:17:49
Problema Sortare prin comparare Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
# include <cstdio>
using namespace std;
int n,i,a[500001];
void intercls(int st, int m, int dr)
{
    int i,j,k;
    int aux[500001];
    i=st;j=m+1;k=st;
    while(i<=m && j<=dr)
    {
        if(a[i]<a[j])
        {
            aux[k++]=a[i];
            ++i;
        }
        else
        {
            aux[k++]=a[j];
            ++j;
        }
    }
    if(i<=m)
        for(j=i;j<=m;++j)
            aux[k++]=a[j];
    else
        for(i=j;i<=dr;++i)
            aux[k++]=a[i];
    for(i=st;i<=dr;++i)
        a[i]=aux[i];
}
void msort(int i, int j)
{
    int m;
    if(i<j)
    {
        m=(i+j)/2;
        msort(i,m);
        msort(m+1,j);
        intercls(i,m,j);
    }
}
int main()
{
    freopen("algsort.in","r",stdin);
    freopen("algsort.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;++i)
        scanf("%d",&a[i]);
    msort(1,n);
    for(i=1;i<=n;++i)
        printf("%d ",a[i]);
    return 0;
}