By Just Skimming through your Problem statement one can judge its a sorting problem, what you need to do is to analyze which sort will meets your need, if you've small array and planty of space then the following trivial algorithm will meet your requirements. But this trivial algorithm only requires unique element.

Algorithm.
i) Find the MAX of Input Array in O(n) Time.
ii) Allocate the Large Enough Array and Initialize it with -1.
iii) Loop Through the Input Array and increment the counter of output array positions which equates to input_array value.
iv) Print the Ouput Array (where value is not negative).

again this is a tentative solution, you can think of another, I'll prefer if you check the Thomas H Corman Sorting Techniques, which suites your requirement, if you really want to learn the sorting techniques & mathematically inclined you should check "The Art of Computer Programming" By Knuth.