Recently, I have been quite intrigued by the mathematical breakthroughs published by OpenAI and other frontier AI labs, especially in breaking previously conjectured time complexity lower bounds for many well-known problems. I think the community of Codeforces would greatly benefit from seeing some similar discoveries, so this is the first of many blogs on SONoptimized algorithms.

Many Codeforces problems present a scenario with some length variable $$$n$$$, typically around the size of $$$2 \times 10^5$$$. It is also very common to see an array $$$a$$$ of length $$$n$$$, with integer elements $$$a_i \leq 10^9$$$. We will see that, if we must sort these elements, we can actually achieve a time complexity of $$$O(n \log^{1 - \epsilon}n)$$$ time, with $$$\epsilon = 1$$$.

Key observation: $$$n^2 = (2 \times 10^5)^2 = 4 \times 10^{10} \gt \max(a_i)$$$

Consider all $$$a_i$$$ in base $$$n$$$. Because $$$n^2 \gt \max(a_i)$$$, we know that they can all be represented in the form $$$xy_n$$$ (with $$$x = \lfloor a_i/n \rfloor, y = a_i \% n$$$). Now, the following method will suffice to sort the array:

1. Allocate an array $$$L$$$ of $$$n$$$ empty lists
2. Iterate $$$a_1$$$ through $$$a_n$$$, appending $$$a_i$$$ to $$$L_{(a_i \% n + 1)}$$$
3. Empty array $$$a$$$, and iterate $$$L_1$$$ through $$$L_n$$$, concatenating each $$$L_i$$$ to the end of $$$a$$$
4. Empty all the lists within $$$L$$$
5. Iterate $$$a_1$$$ through $$$a_n$$$, appending $$$a_i$$$ to $$$L_{(\lfloor a_i/n \rfloor + 1)}$$$
6. Repeat step (3)

As each step will only take $$$O(n)$$$, the entirety of this sorting process will be linear.

void sort(int n, vector<int>& a) {
  vector<vector<int>> L(n);
  for (int a_i : a) L[a_i % n].push_back(a_i);
  a.clear();
  for (vector<int> L_i : L) for (int a_i : L_i) a.push_back(a_i);
  for (int i = 0; i < n; ++i) L[i].clear();
  for (int a_i : a) L[a_i / n].push_back(a_i);
  a.clear();
  for (vector<int> L_i : L) for (int a_i : L_i) a.push_back(a_i);
}