algo2017_week4_Merge_Sort

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define INF 1e9
#define ALL(o) (o).begin(),(o).end()
#define fo(n) for(int i=0;i<n;i++)
#define fos(o,n) for(int i=o;i<n;i++)
typedef long long LL;
template<typename X> inline X sqr(const X& a) {return a * a;}
template<typename X> inline X abs(const X& a) {return a < 0 ? -a : a;}
#define MAX 65536

int x[MAX] , n;
vector<int> p[16];

void print( int dep ){
    fo( dep ){
        cout << p[i][0];
        for( int j = 1 ; j < n ; ++j ) cout << ' ' << p[i][j];
        cout << endl;
    }
}

void Merge( int L , int M , int R ){
    int l = L , r = M , tmp[ R - L + 1 ] , t = 0;

    while( l < M && r <= R ) tmp[t++] = x[l] < x[r] ? x[l++] : x[r++];

    if( l < M ) while( l < M ) tmp[t++] = x[l++];
    else        while( r <= R ) tmp[t++] = x[r++];

    t = 0;
    fos( L , R + 1 ) x[i] = tmp[t++];
}


void MergeSort( int L , int R , int dep ){
    if( L >= R ) return;

    int mid = ( ( L + R ) >> 1 ) + 1;

    MergeSort( L , mid - 1 , dep - 1 );
    MergeSort( mid , R , dep - 1 );
    Merge( L , mid , R );

    fos( L , R + 1 ) p[dep].pb( x[i] );
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    int t = n;
    n = pow( 2 , n );

    fo( n ) cin >> x[i];

    MergeSort( 0 , n - 1 , t - 1 );

    print( t );

    return 0;
}