#include <fstream>
#include <cstdlib>
#include <ctime>

int part(int *myV, int left, int right, int pivot) {
    int val = myV[pivot];
    std::swap(myV[pivot], myV[right]);
    int ind = left;

    for (int i(left); i < right; i++) {
        if (myV[i] < val) {
            std::swap(myV[i], myV[ind]);
            ind++;
        }
    }

    std::swap(myV[right], myV[ind]);
    return ind;
}

void quicksort(int *myV, int left, int right) {
    if (left >= right) {
        return;
    }

    int pivot = left + (rand() % (left - right));
    //int pos = part(myV, left, right, pivot);

    int val = myV[pivot], l = left, r = right;

    while (l < r) {

        while (myV[l] < val) {
            l++;
        }

        while (myV[r] > val) {
            r--;
        }

        if (l <= r) {
            std::swap(myV[l], myV[r]);
            l++;
            r--;
        }
    }

    //quicksort(myV, left, pos - 1);

    quicksort(myV, left, r);

    //quicksort(myV, pos + 1, right);

    quicksort(myV, l, right);
}

int main() {
    std::ifstream fileIn("algsort.in");
    std::ofstream fileOut("algsort.out");
    srand(time(nullptr));

    int nV;

    fileIn >> nV;

    int *myV = new int[nV];

    for (int i(0); i < nV; i++) {
        fileIn >> myV[i];
    }

    quicksort(myV, 0, nV - 1);

    for (int i(0); i < nV; i++) {
        fileOut << myV[i] << ' ';
    }

    delete[] myV;
    fileIn.close();
    fileOut.close();

    return 0;
}