Dsort

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int key(int a, char *s)
{
	return (int) s[a];
}

void distribution(int(*key)(int a, char *s), int m, char *s, int n)
{
	int count[m];
	int i, k, j = 0;
	int last = 0;
	for (i = 0; i < m; i++)
	{
		count[i] = 0;
	}

	while (j < n)
	{
		k = key(j, s);
		if (k >= 0) count[k]++;
		j++;
	}

	i = 1;
	while (i < m)
	{
		count[i] += count[i - 1];
		i++;
	}

	j = n - 1;
	char *d = (char*) malloc(1000001* sizeof(char));
	while (j >= 0)
	{
		k = key(j, s);
		if (k >= 0)
		{
			i = count[k] - 1;
			count[k] = i;
			d[i] = s[j];
		}

		j--;
	}

	for (i = 0; i < n; i++) s[i] = d[i];
	free(d);
}

int main()
{
	int i;

	char *s = (char*) malloc(1000001* sizeof(char));
	fgets(s, 1000001, stdin);

	distribution(key, 125, s, strlen(s));
	printf("%s", s);
	free(s);
	return 0;
}