/*
 * This code is from "Algorithms in C, Third Edition,"
 * by Robert Sedgewick, Addison Wesley Longman, 1998.
 */

#include <stdio.h>
#include <stdlib.h>

#define less(A, B) ((A)<(B))

#define exch(A, B) { int t = A; A = B; B = t; } 
#define compexch(A, B) if (less(B, A)) exch(A, B)

#define maxN 100000

int aux[maxN];

void insertion(int a[], int l, int r)
  { int i;
    for (i = l+1; i <= r; i++) compexch(a[l], a[i]);
    for (i = l+2; i <= r; i++)
      { int j = i; int v = a[i]; 
        while (v<a[j-1])
          { a[j] = a[j-1]; j--; }
        a[j] = v; 
      } 
  }

void mergeAB(int c[], int a[], int N, int b[], int M )
  { int i, j, k;
    for (i = 0, j = 0, k = 0; k < N+M; k++)
      {
        if (i == N) { c[k] = b[j++]; continue; }
        if (j == M) { c[k] = a[i++]; continue; }
        c[k] = (less(a[i], b[j])) ? a[i++] : b[j++];
      }
  }

void mergesortABr(int a[], int b[], int l, int r)
  { int m = (l+r)/2;
    if (r-l <= 10) { insertion(a, l, r); return; }
    mergesortABr(b, a, l, m);  
    mergesortABr(b, a, m+1, r);
    mergeAB(a+l, b+l, m-l+1, b+m+1, r-m);
  }

void mergesortAB(int a[], int l, int r)
  { int i;
    for (i = l; i <= r; i++) aux[i] = a[i];
    mergesortABr(a, aux, l, r);
  }

int main(int argc, char *argv[])
  { int i, N = atoi(argv[1]), sw = atoi(argv[2]);
    int *a = malloc(N*sizeof(int));
    if (sw) 
      for (i = 0; i < N; i++) 
        a[i] = 1000*(1.0*rand()/RAND_MAX);
    else {
      N=0;
      while (scanf("%d", &a[N]) == 1) N++;
    }
    mergesortAB(a, 0, N-1);
    for (i = 0; i < N; i++) printf("%3d ", a[i]);
    printf("\n");
    return 0;
  }