#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

inline void Swap(int *A, int *B)
{
    int aux = *A;
    *A = *B;
    *B = aux;
}

void PrintArray(FILE *file_out, int *Arr, int Size)
{
    int i;
    for (i = 0; i < Size; ++i)
        fprintf(file_out, "%d ", *(Arr + i));
}

int Partition(int *arr, int low, int high)
{
    srand(time(NULL));
    int random = low + rand() % (high - low + 1);
    int mid = (low + high) >> 1;
    Swap(&arr[random], &arr[mid]);

    int pivot = arr[mid];

    int left = low - 1;
    int right = high + 1;

    while (left < right)
    {
        while (arr[++left] < pivot);

        while (arr[--right] > pivot);

        if (left < right)
        {
            Swap(&arr[left], &arr[right]);
        }
    }

    return right;
}

void QuickSort(int *arr, int low, int high)
{
    if (low < high)
    {
        int pivot = Partition(arr, low, high);

        QuickSort(arr, low, pivot);
        QuickSort(arr, pivot + 1, high);
    }
}

int main()
{
    int i;
    int *arr, size;

    FILE *file_in, *file_out;
    file_in = fopen("algsort.in", "r");
    file_out = fopen("algsort.out", "w");

    fscanf(file_in, "%d", &size);
    arr = (int*)malloc(sizeof(int) * size);
    for (i = 0; i < size; ++i)
        fscanf(file_in, "%d", arr + i);

    QuickSort(arr, 0, size - 1);
    PrintArray(file_out, arr, size);


}