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

void swap(int *x, int *y) {
  int aux = *x;
  *x = *y;
  *y = aux;
}

void partition(int *a, int l, int r, int *i, int *j, int pivot) {
  int k = l;
  *i = l;
  *j = r;

  while (k <= *j) {
    // From left, find the first element greater than
    // or equal to v. This loop will definitely
    // terminate as v is last element
    if (a[k] < pivot) {
      swap(&a[k], &a[*i]);
      (*i)++;
      k++;
    } else if (a[k] > pivot) {
      swap(&a[k], &a[*j]);
      (*j)--;
    } else
      k++;
  }
}

// Here, numsSize is the size = number of elements of the nums array.
void quicksort(int *nums, int lo, int hi) {
  if (hi <= lo) return;
  // int pivotIndex = rand() % numsSize;
  // int pivot = nums[pivotIndex];
  int i, j;
  int pivIndex = lo + rand() % (hi - lo + 1);
  partition(nums, lo, hi, &i, &j, nums[pivIndex]);
  // Recursive calls on smaller arrays.
  quicksort(nums, lo, i - 1);
  quicksort(nums, j + 1, hi);
  // pos+1, ... numsSize-1 (numsSize-1-pos)
}

// Quicksort - primele k - quickselect

int main() {
  int *v, n, i;
  FILE *fp_in, *fp_out;
  fp_in = fopen("algsort.in", "r");
  fp_out = fopen("algsort.out", "w");
  srand(time(NULL));
  fscanf(fp_in, "%d\n", &n);
  v = (int *)malloc(n * sizeof(int));
  for (i = 0; i < n; i++) fscanf(fp_in, "%d ", &v[i]);
  quicksort(v, 0, n - 1);
  for (i = 0; i < n; i++) fprintf(fp_out, "%d ", v[i]);
  fclose(fp_in);
  fclose(fp_out);
  return 0;
}