// 【全程注释解析系列】 应该从第一题开始 ！（我又回到 Acwing 大家庭了~）
/*
这道题，应该是大家梦开始的地方。 hh~
它是一道模版题，即 “需要我们可以轻松地背写”
快速排序与归并排序 都应用了一个比较重要的思想（分而治之）这个我们要当作常识，记下。
排序的应用场景：
1. 在处理大数据集的时候，快排更好
2. 计算机图形学中，Z-buffer算法： 在三维场景渲染中，物体的深度需要进行排序，以确定哪些物体在前，哪些物体在后，快速排序常用于对这些物体按距离进行排序。光线追踪（Ray tracing）： 需要对光线路径中的对象进行排序，以优化场景中的交互计算。
3. 在网络数据包排序、日志记录分析等场景中，快速排序可以用来对大量的请求、时间戳或用户活动日志进行高效排序，帮助开发者识别系统中的瓶颈、分析用户行为等。
…… 总而言之，这是一个很常用的工具！我们不能局限于 只会使用写好的 快排方法，而一定要
自己学会，怎么去写，与理解它的实现思路。
*/
#include <iostream>

using namespace std;

// 经典手法：定义一个 最大上限 maxN
const int maxN = 1e5 + 10;
// 由于写算法题，我们一定不要考虑过多的工程细节。所以，你会很常见
// 类似于这种直接开辟 maxN 长度的数组，方便算法在用 arr 时，不需考虑容量的问题
int arr[maxN]; // 存储数据的数组

void quick_sort(int* q, int l, int r) {
    // 左边界大于等于右边界时，代表着该区间没有元素或只有一个元素
    // 一个元素的区间，自然有序，不需要进行处理！
    if (l >= r) return;
    int x = q[l];  // 基准元素
    // 之所以 i = l - 1, j = r + 1
    // 是因为只要我们从左边界的左边和右边界的右边 开始扫描
    // 恰好可以每一步 都走到预想的 位置。而无需再次 特判
    // 去处理，什么时候多一次 i++ 和 j-- 的问题
    int i = l - 1, j = r + 1;  // 双指针法
    while (i < j) { // 一回合的扫描，肯定只局限于两个指针未相遇的时候
        // 左边找到大于等于x的元素, 就停下来
        do i++; while (q[i] < x);
        // 右边找到小于等于x的元素，就停下来
        do j--; while (q[j] > x);
        // 如果找到的这俩元素，互相的位置是合理的
        // 那么就需要交换它俩的位置
        // 从而实现在基准点左侧是小于等于它的，基准点的右侧是大于等于它的
        if (i < j) {
            // 交换i和j处的元素
            int temp = q[i];
            q[i] = q[j];
            q[j] = temp;
        }
    }
    // 递归排序左半部分和右半部分
    // 依赖于 j 来分区间，是取决于 你基准点 q[l]
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

int main(void) {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &arr[i]);
    }
    quick_sort(arr, 0, n - 1);
    for (int i = 0; i < n; ++i) {
        printf("%d ", arr[i]);
    }
    return 0;
}
/*
上述代码，样例的处理过程 => 
大家可以自己拿笔 写一写，其实模版题 是不难的，几乎就是让你背写
1: 3 1 2 4 5 j: 2
2: 2 1 3 4 5 j: 1
3: // 2 1 // 3 4 5
4: // 12 // 3 4 5
5: 1 2 3 4 5
*/