/* prog7.3.c */
#include <stdio.h>
#include <stdlib.h>

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

#define M 1000

/* Rotinas de pilha - prog4.4.c */

static int *s;
static int N;
void STACKinit(int maxN)
  { s = malloc(maxN*sizeof(int)); N = 0; }
int STACKempty()
  { return N == 0; }
void STACKpush(int item)
  { s[N++] = item; }
int STACKpop()
  { return s[--N]; }

/* Fim das rotinas de pilha */

int partition(int a[], int l, int r)
  { int i = l-1, j = r; int v = a[r];
    for (;;)
      { 
        while (less(a[++i], v)) ;
        while (less(v, a[--j])) if (j == l) break;
        if (i >= j) break;
        exch(a[i], a[j]);
      }
    exch(a[i], a[r]);
    return i;
  }

#define push2(A, B)  STACKpush(B); STACKpush(A);
void quicksort(int a[], int l, int r)
  { int i;
    STACKinit(M); push2(l, r);
    while (!STACKempty())
      {
        l = STACKpop(); r = STACKpop(); 
        if (r <= l) continue;
        i = partition(a, l, r);
        if (i-l > r-i)
          { push2(l, i-1); push2(i+1, r); }
        else
          { push2(i+1, r); push2(l, i-1); }
      }
  }

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++;
    }
    quicksort(a, 0, N-1);
    for (i = 0; i < N; i++) printf("%3d ", a[i]);
    printf("\n");
    return 0;
  }