quickSort

//Quicksort(A, l, k) -> A[l]...A[h]
//A - массив
//l, h - индексы массива
//
//if l < h then
//    p <- Partition(A, l, k)
//    Quicksort(A, l, p - 1)
//    Quicksort(A, p + 1, k)
//
//
//A[0]...A[p - 1] < A[p] <= A[p + 1]...A[n - 1]
//Partition(A, l, k) -> b
//    p <- PickElement(A)
//    Swap(A[p], A[k])
//    b <- l
//    for i <- l to k
//        if Compare(A[i], A[k]) < 0
//            Swap(A[b], A[i])
//            b++
//    Swap(A[k], A[b])
//return b




#include <iostream>
#include <vector>

void quickSort(std::vector<int>& array, int leftIndex, int rightIndex) {
    if (leftIndex <= rightIndex) {
        int pivot = (array[leftIndex] + array[(leftIndex + rightIndex) / 2] + array[rightIndex]) / 3;
        int start = leftIndex, end = rightIndex;

        while (start <= end) {
            while (array[start] < pivot) {
                start++;
            }
            while (array[end] > pivot) {
                end--;
            }
            if (start <= end) {
                if (start < end) {
                    std::swap(array[start], array[end]);
                }

                start++;
                end--;
            }
        }
        quickSort(array, leftIndex, end);
        quickSort(array, start, rightIndex);
    } else {
        return;
    }
}



int main() {



    int size;
    std::cin >> size;

    std::vector<int> array(size);
    for (auto& element : array) {
        std::cin >> element;
    }

    quickSort(array, 0, size - 1);

    for (auto element : array) {
        std::cout << element << ' ';
    }
    return 0;
}