Suppose you are given a list of n positive integers which are all less than 1000. Describe how you would write an algorithm that sorts these integers from smallest to largest and has a runtime in O(n), and prove that this algorithms runtime is indeed in O(n).