package ld1;
import java.util.Scanner;
public class ld1161rdb107 {
	int co = 0;
	int a[] = new int [co];
	int b[] = new int [co];
	int c[] = new int [co];
	int tmp[] = new int[co];
	public static void firstMethod(int[] a) {
		boolean b = true;
		while (b == true) {
			b = false;
			for(int i = 0; i < a.length-1; i = i+2){
				if(a[i] > a[i+1]){
					a[i+1]=a[i]+a[i+1];
	                a[i]=a[i+1]-a[i];
	                a[i+1]=a[i+1]-a[i];
	                b = true;
				}
			}
			for(int i = 1;i < a.length-1; i = i+2){
				if(a[i] > a[i+1]){
					a[i+1]=a[i]+a[i+1];
	                a[i]=a[i+1]-a[i];
	                a[i+1]=a[i+1]-a[i];
	                b = true;
				}
			}
		}
	}

	public static void secondMethod(int[] a) {
		int k, i, j, ri, rj;

        int b[] = new int [a.length];

        int c[] = new int [a.length];

        int tmp[] = new int [a.length];

        int len = 1;



        for (i=0;i<a.length;i++)

              b[i] = a[i];



        while(len<a.length){

              int N=0;

              for(k=0;k<a.length;k=k+2*len){

                    N=k;

                    i=k;

                    j=k+len;



                    if ((k+len)<a.length)

                          ri=k+len;

                    else

                          ri=a.length;



                    if ((k+2*len)<a.length)

                          rj = k+2*len;

                    else

                          rj = a.length;



                    while((i<ri)&&(j<rj)){

                          if (b[i]<b[j]){

                                c[N] = b[i];

                                i++;

                                N++;

                          } else {

                                c[N] = b[j];

                                j++;

                                N++;

                          }

                    }



                    while (i<ri){

                          c[N] = b[i];

                          i++;

                          N++;

                    }



                    while (j<rj){

                          c[N] = b[j];

                          j++;

                          N++;

                    }

              }



              len=2*len;

              for (i=0; i<a.length; i++){

                    tmp[i] = b[i];

                    b[i] = c[i];

                    c[i] = tmp[i];

              }



        }



        for (i=0; i<a.length; i++)

              a[i] = b[i];



  }

	public static void main(String[] args) {

		System.out.println("Heinrihs Skrodelis RDBI0 161RDB107");
		int i, met, mSize, z;
		System.out.println("method:");
		Scanner sc = new Scanner((System.in));
		if (sc.hasNextInt()) {
			met = sc.nextInt();
			if (met > 2 || met < 1) {
				System.out.println("input-output-error");
				sc.close();
				return;
			}
		} else {
			System.out.println("input-output-error");
			sc.close();
			return;
		}
		System.out.println("count:");
		if (sc.hasNextInt()) {
			z = sc.nextInt();
			mSize = z;
		} else {
			System.out.println("input-output-error");
			sc.close();
			return;
		}

		System.out.println("items:");
		int a[] = new int [mSize];
		if (sc.hasNextInt()) {
			for (i = 0; i < mSize; i++) {
				a[i] = sc.nextInt();
			}
		} else {
			System.out.println("input-output-error");
			sc.close();
			return;
		}
		sc.close();
		long startTime = System.nanoTime();
		if (met == 1) {
			firstMethod(a);
		} else {
			secondMethod(a);
		}
		System.out.println("sorted:");
			for(i = 0; i < z; i++) {
				System.out.print(a[i] + " ");
			}

			long endTime = System.nanoTime();
			System.out.println("");
			System.out.println("Took "+(endTime - startTime)/1000 + " microseconds");

		}
}