题目信息：

限制

时间限制：1s

空间限制：3GB

题目描述

有 $n\le 10^5$ 个整数，每个整数 $a_i$ 在区间 $[0,10^{6}]$，要对这些整数进行升序排序。

数据范围

$n\le 10^5, a_i\in[0,10^6]$

样例

样例输入 #1

3
2
1
1

样例输出 #1

1
1
2

代码：

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    int a[100005];
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    sort(a,a+n);
    for(int i=0;i<n;i++){
        cout << a[i] << endl;
    }
    return 0;
}

评测结果：

$\colorbox{purple}{\color{white}Time Limit Error 超时。样例通过：3/10}$

貌似是时间复杂度太高了。

请问是否有一个排序算法的时间复杂度 $\le O(n \log n)$？