Sometimes we can assume the items to be sorted have keys which are integers in the range 1, . . . , m. In this case, the Counting Sort algorithm can sort n items in O(n + m) time.

i. Describe the Counting Sort algorithm in detail.

ii. Justify the O(n + m) running time bound.

iii. Prove that the Counting Sort algorithm is stable, that is, it always leaves items with the same key value in their original order.