Sorting $n^2$ numbers which consist of numbers from 1 to $n$ I wish to sort $n^2$ numbers which all come from the set $\{1,2,3,...,n\}$, i.e duplications are allowed. I know I can just use
merge sort which has complexity $\mathcal{O}(n^2\log (n))$, but I was wondering if it was possible to do better since I know all the numbers will be coming out of $\{1,2,3,...,n\}$.
If there is a special name for this type of problem please let me know. Any references or answers are greatly appreciated.
Given your contraints, I think Counting sort or Radix sort will do the job.

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

https://en.wikipedia.org/wiki/Radix_sort