#include<iostream>
using namespace std;

void merge(int *a, int p, int q, int r, int *to)
{
    int i=p;
    int j=q;
    while( i<q && j<r )
    {
        if( a[i] <= a[j] )
            *to++ = a[i++];
        else
            *to++ = a[j++];
    }

    while( i<q )
        *to++ = a[i++];
    while( j<r )
        *to++ = a[j++];
}

void sort( int* a, int size )
{
    int *tmp = new int[size];
    int *src = a;
    int *dst = tmp;
    for( int i=1; i<=size; i=i*2)
    {
        for( int j=0; j<size; j=j+2*i)
        {
            merge( src, j, min(j+i, size), min(j+2*i,size), dst+j );
        }
        swap(src, dst);
    }
    if( src!=a )
        merge(tmp, 0, size, size, a);

    delete [] tmp;
}
int main()
{
    const int size = 6;
    int tab[] = {9,4,3,7,12,1};
    sort(tab, size);
    for( int i=0; i<size; i++ )
        cout<<tab[i]<<" ";
    cout<<endl;
}