#include <iostream>

 #include <vector>

 #include <ctime>

 using namespace std;

 // Counting Sort an Array with each element in [0, upper]

 void countingSort(vector<int>& nums, int upper) {

     vector<int> counts(upper + , );

     for (int i = ; i < (int)nums.size(); i++)

         counts[nums[i]]++;

     for (int i = ; i <= upper; i++)

         counts[i] += counts[i - ];

     vector<int> sorted(nums.size());

     for (int i = (int)nums.size() - ; i >= ; i--) {

         sorted[counts[nums[i]] - ] = nums[i];

         counts[nums[i]]--;

     }

     swap(nums, sorted);

 }

 void print(vector<int>& nums) {

     for (int i = ; i < (int)nums.size(); i++)

         printf("%d ", nums[i]);

     printf("\n");

 }

 void countingSortTest(int len, int upper) {

     vector<int> nums(len);

     srand((unsigned)time(NULL));

     for (int i = ; i < len; i++)

         nums[i] = rand() % (upper + );

     print(nums);

     countingSort(nums, upper);

     print(nums);

 }

 int main(void) {

     countingSortTest(, );

     system("pause");

     return ;

 }