I think like that
Firstly, I must use count sort or heap sort?
Then count maximal number and write it.

Am I right?

The simplest way is Qsort and out mas[n div 2]  O(n*lgn)
Read other thread for fast O(n)

Thanks to you KIRILL(ArcSTU)