Counting sort: https://en.wikipedia.org/wiki/Counting_sort

Yes, with counting sort algorithm.

Here lies your answer

I'm pretty sure we've all heard that the best sorting worst-case scenario is $$$\mathcal{O} (N \log N)$$$. What people really mean is that the best comparison sort is worst case $$$\mathcal{O} (N \log N)$$$. Comparison sort basically means that we assume nothing about the items except that they can be compared with another via some oracle.

Indeed, one can prove straight-forwardly that the best comparison sort is worst-case $$$\mathcal{O} (N \log N)$$$. One can find a proper proof on the internet, but they way I think of it is that we have $$$N!$$$ permutations and by checking the relation between $$$u, v$$$, we halve the number of possible permutations. So we need $$$\log_2(N!) \approx N \log N$$$ "queries." Again, this is very crude, but I find it more intuitive than the pedantic proofs online.

Now, if you want to assume more than just "items can be compared," then yes, sorting can be done in $$$\mathcal{O}(N)$$$. This can be done using radix sort, for example, if you assume that keys can be partitioned into "boxes". If you assume further that the keys are small integers, then you can use counting sort, which is also $$$\mathcal{O}(N)$$$.

But personally, I think radix and counting sort are cheap :P.

The end of my sorting rant.

In competitive programming you should not waste time on implementing sorting algorithms, instead use inbuilt STL sort function.

For implementation you may prefer to This