Sorting $n^2$ numbers which consist of numbers from 1 to $n$
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