import java.util.*;
import java.lang.*;

class Rextester
{ public static void main(String args[])
  { int N,i,k,t,q,r,p0,q0,s0;
    N=30;
    int[] A = new int[N];
    int[] B = new int[N];
    for (i=0; i<N; i++) A[i]=(int) (Math.random()*100);
    for (i=0; i<N; i++) System.out.print(A[i]+" ");
    System.out.println();   

    k = 1;
    while (k<N)
    { t = 0;
      while ((t+k) <= N) 
      { q = t + k;
        if (t + 2*k >= N)  r = N;
        else               r = t + 2*k;
        p0 = t;
        q0 = q;
        s0 = t;
        while ((p0 != q) || (q0 != r))
        { if ((p0 < q) && (((q0 == r) || ((q0 < r) && (A[p0] <= A[q0])))))
               {B[s0] = A[p0]; p0++; s0++;}
          else {B[s0] = A[q0]; q0++; s0++;}
        }   
        t = r;
      }
      k = k * 2; 
      for (i = 0; i < N; i++) A[i] = B[i]; 
    }
    for (i = 0; i < N; i++) System.out.print(A[i]+" ");
  }
}