#include <iostream>
using namespace std;

void print_array(int* array, int size)
{
	for (int i=0; i<size;  i++)
		cout << array[i] << " ";

	cout << endl;
}

void count_sort(int* array, int size, int range)
{
	int* counts = new int[range];
	int* sorted = new int[size];
	int i;
	
	memset(counts, 0, sizeof(int) * range);

	// first, count the elements
	for (i=0; i<size; i++)
	{
		counts[array[i]]++;
	}

	print_array(counts, range);

	// now the counts stores all the counts of every element
	// calculate the position of the element
	for (i=1; i<range; i++)
	{
		counts[i] = counts[i] + counts[i-1];
	}

	print_array(counts, range);

	// put the elements in the right position to the sorted array
	for (i=0; i<size; i++)
	{
		sorted[counts[array[i]]-1] = array[i];
		counts[array[i]]--;
	}

	// copy back to the original
	memcpy(array, sorted, sizeof(int) * size);
	
	delete[] sorted;
	delete[] counts;
}

void main()
{
	int* array;
	int size;
	int range;
	cout << "input the size of array:";
	cin >> size;

	cout << "input the max elements of array:";
	cin >> range;

	array = new int[size];
	// make sure the data are all in the range 
	for (int i=0; i<size; i++)
	{
		array[i] = rand()%range;
	}

	print_array(array, size);
	count_sort(array, size, range);
	print_array(array, size);

	delete[] array;
}